Parcours en largeur d'un graphe

Parcours en largeur d'un graphe (BFS).

Au départ tous les sommets sont blancs.

 1 - on grise un sommet choisi comme point de départ, que l'on numérote 1.
 2 - on grise les voisins du sommet gris de plus petit numéro, en les numérotant au fur et à mesure de leur découverte -- 
 à condition qu'ils ne soient ni gris, ni noirs.
 3 - on noircit ce gris de plus petit numéro.
 4 - on recommence au point 2 tant qu'il reste des sommets gris.

Dans le descriptif utilisé ci-dessus, on voit qu'à tout moment c'est le premier sommet qui a été grisé (et qui est encore gris) qui est dégrisé (ici noirci). Il s'agit de la notion de file.

Ré-énonçons cet algorithme avec la notion de file. Au départ la file est vide.

 1 - on enfile un sommet choisi comme point de départ.
 2 - on enfile les voisins du sommet tête de file -- à condition qu'ils ne soient pas déjà dans la file ou déjà passés dans 
 la file.
 3 - on défile (c'est à dire : on sort la tête de file de la file).
 4 - on recommence au point 2 tant que la file n'est pas vide.

Exemple : parcours en largeur d'un arbre.

Le pdf suivant illustre les étapes possibles d'un parcours en largeur d'un arbre : visionner le diaporama.

On choisit dans ce déroulement de toujours enfiler en priorité le fils le plus à gauche. Ce choix est bien sûr arbitraire, on peut choisir un autre ordre.

Une notion de distance.

1. Un sommet a est à une distance 1 d'un sommet s du graphe s'il existe une arête reliant s et a.
2. Un sommet b est à une distance 2 de s s'il n'est pas à distance 1 et s'il existe une arête entre un sommet a à distance 1 de s et ce sommet b. En d'autres termes, le plus court chemin de s à b dans le graphe emprunte deux arêtes.
3. Un sommet c est à une distance 3 de s s'il n'est pas à distance 1 ou 2 et s'il existe une arête entre un sommet b à distance 2 de s et ce sommet c. En d'autres termes, le plus court chemin de s à c dans le graphe emprunte trois arêtes.
4. ...

L’algorithme de parcours en largeur va visiter en premier lieu toutes les pages à distance 1 du départ, puis toutes les pages à distance 2 du départ, puis toutes les pages à distance 3. . .C’est en fait cette propriété qui donne son nom à ce type de parcours.

Programmation python du parcours

Représentation de la structure de graphe.

On utilisera un dictionnaire python pour la structure de graphe.

Le graphe G ci-dessous a 8 sommets nommés a, b, c, d, e, f, g, h. Les voisins de a sont b et c; les voisins de b sont a, d, e ...

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’]

Une représentation graphique :

Descriptif du programme attendu.

Avec la représentation d’un graphe par un dictionnaire comme précédemment, programmer en langage python le BFS avec les variables suivantes :

1. Un dictionnaire P. En fin de parcours, pour tout sommet s du graphe P[s] sera le père de s, c’est à dire le sommet à partir duquel le sommet s a été découvert lors du parcours.
2. Un dictionnaire couleur. Pour tout sommet s, couleur[s] vaut blanc si le sommet s n’est pas passé dans la file, gris s’il est dans la file, noir lorsqu’il est sorti de la file.
3. Une liste Q utilisée comme file (fifo) : on enfile un sommet lorsqu’il est découvert, on le défile lorsqu’il est terminé (traitement prioritaire des sommets découverts au plus tôt).

Illustration.

Le pdf suivant illustre les étapes possibles d'une exécution du programme : visionner le diaporama.

Un programme possible

Le code suivant répond à la demande précédente :

def bfs(G,s) :
	couleur=dict()
	for x in G : couleur[x]='blanc'
	P=dict()
	P[s]=None
	couleur[s]='gris'
	Q=[s]
	while Q :
		u=Q[0]
		for v in G[u] :
			if couleur[v]=='blanc' :
				P[v]=u
				couleur[v]='gris'
				Q.append(v)
		Q.pop(0)
		couleur[u]='noir'
	return P
	
	
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'))

ou en ne gardant que le nécessaire :

def bfs(G,s) :
	P,Q={s :None},[s]
	while Q :
		u=Q.pop(0)
		for v in G[u] :
			if v in P : continue
			P[v]=u
			Q.append(v)
	return P
	
	
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'))