Breadth-First Search en Python

Version imprimable

Bonjour,

Voila je suis entrain de travailler sur un programme de BFS en python mais mon problème est que j'ai réussi à trouvers des programmes en python comme celui-là :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def dfs(graph, start): visited, stack = set(), [start] while stack: vertex = stack.pop() if vertex not in visited: visited.add(vertex) stack.extend(graph[vertex] - visited) return visited graph = {'A': set(['B', 'C']), 'B': set(['A', 'D', 'E']), 'C': set(['A', 'F']), 'D': set(['B']), 'E': set(['B', 'F']), 'F': set(['C', 'E'])} print(dfs(graph, 'A')) # # {'E', 'D', 'F', 'A', 'C', 'B'}
Je voudrai pouvoir utiliser ce programme avec une matrice d'adjacence, donc une liste de liste composé de 1 et de 0, et non un dictionnaire pour pouvoir au lieu de retourner l'ordre des sommets visités retourner leur distance au sommet de départ et s'il n'a pas été visités -1:

Code:

assert BFS([[0, 1, 1, 0, 0], [0, 0, 1, 0, 0], [0, 1, 0, 1, 0], [0, 0, 0, 0, 0], [1, 0, 1, 0, 0]],0) == [0, 1, 1, 2, -1]

Merci de votre aide

29/03/2018, 11h59
wiztricks

Salut,

Soit vous convertissez la matrice en graphe, soit vous utilisez le code que vous aviez posté dans les posts précédents.

- W

Merci de votre réponse,

Mais dans les post précédents c'étaient pour un parcours en profondeur et non en largeur.
J'ai essayer de faire cela mais je n'ai pas une valeur cohérente de la distance :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
def bfs2(mat, start):
    visited = set()
    distance = [-1 for i in range(len(mat))]
    distance[start] = 0
    temp = 1
    visited.add(start)
    for i in range(len(mat)):
        for j in range(len(mat)):
            if mat[i][j] == 1 and j not in visited:
                distance[j] = temp
                visited.add(j)
        temp = temp + 1
    return distance

Cela me donne :

Code:

1
2
mat1 = [[0,1,1,0], [1,0,1,0], [1,1,0,1], [0,0,1,0]]
print(bfs2(mat1, 0)) #[0, 1, 1, 3] au lieu de [0, 1, 1, 2]

Si quelqu'un a une idée ....

Salut,
Essayez avec çà:

Code:

1
2
3
4
5
6
7
8
9
def dfs2(matrix, start):
    visited, stack = [], [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.append(vertex)
            adjency = [ x for x, e in enumerate(matrix[vertex]) if e and x not in visited ]
            stack.extend(adjency)
    return visited

29/03/2018, 22h39
nono9196

Merci pour la fonction mon problème est que j'ai besoin d'afficher la distance de chaque point au point de départ et je n'arrive pas à avoir une distance qui soit cohérente comme sur mon poste au - dessus.
29/03/2018, 23h20
wiztricks

Citation:

Envoyé par nono9196

Merci pour la fonction mon problème est que j'ai besoin d'afficher la distance de chaque point au point de départ et je n'arrive pas à avoir une distance qui soit cohérente comme sur mon poste au - dessus.

Mouais, çà serait mieux de déjà vérifier que votre code est un BFS: pas de stack et pas d'ajout à la fin, pour moi, c'est autre chose. Après les distances, c'est encore autre chose.

- W
29/03/2018, 23h23
nono9196

En faite je ne connais pas trop c'est fonction que sont pop et extend du coup j'ai voulu le faire seulement avec ce que je connaissais mais je crois que l'essai n'est pas concluant.
29/03/2018, 23h50
lg_53
Code:

1 2 list1.extend(list2) <=> list1 = list1 + list2 a = list1.pop() <=> a = list1[-1]; del list1[-1] ### Efface le dernier élément de la liste
Et si vous ne connaissez pas la fonction del vous pouvez très bien remplacer :

Code:

del a[-1] <=> a=a[:-1]

Donc tout est faisable avec les fonctions dont vous avez connaissances.

Sinon une petite lecture de la documentation Python sur les listes permettera de faire le point sur les méthodes sur les listes :
https://docs.python.org/3/tutorial/datastructures.html