Parcours en profondeur d'un graphe

Parcours en profondeur d'un graphe.

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 - si le sommet gris de plus grand numéro, s,  a des voisins blancs :
     alors on grise un voisin de s, on le numérote par le numéro suivant disponible,
     sinon on noircit s.
 3 - 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 dernier sommet qui a été grisé (et qui est encore gris) qui est dégrisé (ici noirci). Il s'agit de la notion de pile.

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

 1 - on empile un sommet choisi comme point de départ.
 2 - si le sommet de la pile présente des voisins non encore entrés dans la pile, 
     alors on empile l'un de ses voisins
     sinon on dépile (c'est à dire on enlève l'élément au sommet de la pile).
 3 - on recommence au point 2 tant que la pile n'est pas vide.

Exemple : parcours en profondeur d'un arbre.

Le pdf suivant illustre les étapes possibles d'un parcours en profondeur 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.

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 DFS 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 encore découvert, gris s’il est déjà découvert mais non encore fermé (c’est à dire si l’algorithme n’ a pas encore découvert tous ses voisins), noir lorsque ce sommet est fermé.
3. Une liste Q utilisée comme pile (lifo) : on empile un sommet lorsqu’il est découvert, on le dépile lorsqu’il est terminé (traitement prioritaire des sommets découverts au plus tard).

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 dfs(G,s) :
	couleur=dict()
	for v in G :couleur[v]='blanc'
	P=dict()
	P[s]=None
	couleur[s]='gris'
	Q=[s]
	while Q :
		u=Q[-1]
		R=[y for y in G[u] if couleur[y]=='blanc']
		if R :
			v=R[0]
			couleur[v]='gris'
			P[v]=u
			Q.append(v)
		else :
			Q.pop()
			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(dfs(G,'g'))

ou en ne gardant que le nécessaire :

import random

def dfs(G,s) :
	P,Q={s :None},[s]
	while Q :
		u=Q[-1]
		R=[y for y in G[u] if y not in P]
		if R :
			v=random.choice(R)
			P[v]=u
			Q.append(v)
		else :
			Q.pop()
	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(dfs(G,'g'))