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 : Sélectionner tout - Visualiser dans une fenêtre à part
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 : Sélectionner tout - Visualiser dans une fenêtre à part
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