Implémentation Python du parcours en largeur dans les graphes (BFS)

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))

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *