Breadth first search

Distance.

Il a été précisé dans le cours que le parcours en largeur d'un graphe se faisait du plus proche au plus éloigné de la racine. Revoir au besoin le paragraphe sur la distance.

Modifier le programme python du parcours en largeur tel qu'il est proposé dans le cours de telle façon qu'il retourne un dictionnaire des distances au sommet initial.

Par exemple pour le graphe
représentation
parcouru en largeur en partant de b, le programme devra retourner le dictionnaire :
distance = { 'b' :0, 'e' : 1, 'a' : 1, 'd' : 1, 'c' : 2, 'f' : 2, 'g' : 2, 'h' : 3 }.

Code python : 


def bfs(G,s) :
	couleur=dict()
	for x in G : couleur[x]='blanc'
	P=dict()
	distance=dict()
	P[s]=None
	distance[s]=0
	couleur[s]='gris'
	Q=[s]
	while Q :
		u=Q[0]
		for v in G[u] :
			if couleur[v]=='blanc' :
				P[v]=u
				distance[v]=distance[u]+1
				couleur[v]='gris'
				Q.append(v)
		Q.pop(0)
		couleur[u]='noir'
	return distance
	
	
G=dict()
G['a']=['b','c']
G['b']=['a','d','e']
G['c']=['a','d']
G['d']=['b','c','e']
G['e']=['b','d','f','g']
G['f']=['e','g']
G['g']=['e','f','h']
G['h']=['g']


print(bfs(G,'b'))

{'a': 1, 'e': 1, 'd': 1, 'c': 2, 'g': 2, 'f': 2, 'b': 0, 'h': 3}