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
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 }.
Résolution de l'exercice "Distance".
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}