Cet article fait suite à celui qui porte sur l’algorithme BFS ici : https://128mots.com/index.php/2020/02/11/parcours-en-largeur-dans-les-graphes-bfs/
L’implémentation Python de cet algorithme est la suivante :
from collections import deque
def bfs(graph, vertex):
queue = deque([vertex])
distance = {vertex: 0}
pere = {vertex: None}
while queue:
t = queue.popleft()
for voisin in graph[t]:
if voisin not in distance:
queue.append(voisin)
distance[voisin] = distance[t] + 1
pere[voisin] = t
return distance, pere
#Liste d'ajacence du graphe
graph = {
'A': ['B','C'],
'B': ['A','C', 'D'],
'C': ['D'],
'D': ['C','A']
}
distance,pere = bfs(graph,'A')
print("Distances" + str(distance))
print("Pere = " + str(pere))
