DFS avec python
Nous nous baserons dans cette partie sur le même modèle de graphe que celui utilisé pour la description du parcours en largeur :
L'implémentation Python à l'aide d'un dictionnaire sera la suivante:
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']
Avec la représentation d'un graphe par un dictionnaire comme précédemment, nous allons programmer en langage Python le DFS avec les variables suivantes :
P tel que, 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 que parcours.couleur tel que, pour tout sommet S, couleur[S] soit blanc si le sommet S n'est pas passé dans la
file, gris si le sommet S est dans la file et noir si le sommet S est sorti de la file.Q utilisée comme pile (LIFO).Un déroulement de la fonction avec l'appel dfs(G, 'g'):
 |
P = {'g' : None} Q = ['g'] Découverts(gris ou noirs) = ['g'] Fermés(noirs) = [] |
|---|---|
 |
P = {'g':None , 'e':'g'} Q = ['g', 'e'] Découverts(gris ou noirs) = ['g', 'e'] Fermés(noirs) = [] |
 |
P = {'g':None , 'e':'g' , 'b':'e' Q = ['g', 'e', 'b'] Découverts(gris ou noirs) = ['g', 'e', 'b'] Fermés(noirs) = [] |
 |
P = {'g':None , 'e':'g' , 'b':'e' , 'a':'b' Q = ['g', 'e', 'b', 'a'] Découverts(gris ou noirs) = ['g', 'e', 'b', 'a'] Fermés(noirs) = [] |
 |
P = {'g':None , 'e':'g' , 'b':'e' , 'a':'b' , 'c':'a'} Q = ['g', 'e', 'b', 'a', 'c'] Découverts(gris ou noirs) = ['g', 'e', 'b', 'a', 'c'] Fermés(noirs) = [] |
 |
P = {'g':None , 'e':'g' , 'b':'e' , 'a':'b' , 'c':'a' , 'd':'c'} Q = ['g', 'e', 'b', 'a', 'c', 'd'] Découverts(gris ou noirs) = ['g', 'e', 'b', 'a', 'c', 'd'] Fermés(noirs) = [] |
 |
P = {'g':None , 'e':'g' , 'b':'e' , 'a':'b' , 'c':'a' , 'd':'c'} Q = ['g', 'e', 'b', 'a', 'c'] Découverts(gris ou noirs) = ['g', 'e', 'b', 'a', 'c', 'd'] Fermés(noirs) = ['d'] |
 |
P = {'g':None , 'e':'g' , 'b':'e' , 'a':'b' , 'c':'a' , 'd':'c'} Q = ['g', 'e', 'b', 'a'] Découverts(gris ou noirs) = ['g', 'e', 'b', 'a', 'c', 'd'] Fermés(noirs) = ['d', 'c'] |
 |
P = {'g':None , 'e':'g' , 'b':'e' , 'a':'b' , 'c':'a' , 'd':'c'} Q = ['g', 'e', 'b'] Découverts(gris ou noirs) = ['g', 'e', 'b', 'a', 'c', 'd'] Fermés(noirs) = ['d', 'c', 'a'] |
 |
P = {'g':None , 'e':'g' , 'b':'e' , 'a':'b' , 'c':'a' , 'd':'c'} Q = ['g', 'e'] Découverts(gris ou noirs) = ['g', 'e', 'b', 'a', 'c', 'd'] Fermés(noirs) = ['d', 'c', 'a', 'b'] |
 |
P = {'g':None , 'e':'g' , 'b':'e' , 'a':'b' , 'c':'a' , 'd':'c' ,'f':'e'} Q = ['g', 'e', 'f'] Découverts(gris ou noirs) = ['g', 'e', 'b', 'a', 'c', 'd', 'f'] Fermés(noirs) = ['d', 'c', 'a', 'b'] |
 |
P = {'g':None , 'e':'g' , 'b':'e' , 'a':'b' , 'c':'a' , 'd':'c' ,'f':'e'} Q = ['g', 'e'] Découverts(gris ou noirs) = ['g', 'e', 'b', 'a', 'c', 'd', 'f'] Fermés(noirs) = ['d', 'c', 'a', 'b', 'f'] |
 |
P = {'g':None , 'e':'g' , 'b':'e' , 'a':'b' , 'c':'a' , 'd':'c' ,'f':'e'} Q = [] Découverts(gris ou noirs) = ['g', 'e', 'b', 'a', 'c', 'd', 'f'] Fermés(noirs) = ['d', 'c', 'a', 'b', 'f', 'e'] |
 |
P = {'g':None , 'e':'g' , 'b':'e' , 'a':'b' , 'c':'a' , 'd':'c' ,'f':'e' , 'h':'g'} Q = ['g', 'h'] Découverts(gris ou noirs) = ['g', 'e', 'b', 'a', 'c', 'd', 'f', 'h'] Fermés(noirs) = ['d', 'c', 'a', 'b', 'f', 'e'] |
 |
P = {'g':None , 'e':'g' , 'b':'e' , 'a':'b' , 'c':'a' , 'd':'c' ,'f':'e' , 'h':'g'} Q = ['g'] Découverts(gris ou noirs) = ['g', 'e', 'b', 'a', 'c', 'd', 'f', 'h'] Fermés(noirs) = ['d', 'c', 'a', 'b', 'f', 'e' 'h'] |
 |
P = {'g':None , 'e':'g' , 'b':'e' , 'a':'b' , 'c':'a' , 'd':'c' ,'f':'e' , 'h':'g'} Q = [] Découverts(gris ou noirs) = ['g', 'e', 'b', 'a', 'c', 'd', 'f', 'h'] Fermés(noirs) = ['d', 'c', 'a', 'b', 'f', 'e', 'h', 'g'] |
L'arborescence associée au parcours peut donc être modélisée de la façon suivante :
dfs() pourrait donc être :
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
De façon plus concise:
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
Et si l'on veut expliciter un peu plus l'utilisation d'une pile:
import random
class Maillon:
def __init__(self, valeur, suivant=None):
self.valeur = valeur
self.suivant = suivant
class Pile:
def __init__(self):
self.taille = 0 # nombre d'assiettes dans la pile
self.sommet = None
def empiler(self, valeur):
self.sommet = Maillon(valeur, self.sommet)
self.taille += 1
def depiler(self):
if self.taille > 0:
valeur = self.sommet.valeur
self.sommet = self.sommet.suivant
self.taille -= 1
return valeur
def estVide(self):
return self.taille == 0
def lireSommet(self):
return self.sommet.valeur
def dfs(G,s) :
P = {s: None}
Q = Pile()
Q.empiler(s)
while not(Q.estVide()) :
u = Q.lireSommet()
R=[y for y in G[u] if y not in P]
if R :
v=random.choice(R)
P[v]=u
Q.empiler(v)
else :
Q.depiler()
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'))
Pour créer un labyrinthe, une technique consiste à considérer une grille comme un graphe: les voisins d'une cellule sont les cellules ayant un côté commun avec la cellule.
On part d'une cellule et on parcourt en profondeur ce graphe, en choisissant comme ci-dessus au hasard le voisin à chaque étape.
Lorsque le parcours est terminé, on fait tomber les murs entre une cellule et son père (père au sens utilisé ci-avant dans le parcours en profondeur).
Plutôt que de définir explicitement le graphe, on définit une fonction voisinage qui construira la liste des voisins pour chaque cellule.
La fonction dedale() dans le code ci-dessous ne sert ensuite qu'à tracer le résultat (on utilise une grille environ deux fois plus grande pour avoir la place des couloirs et des murs).
Remarque: comme le parcours en profondeur est naturellement récursif, vous retrouverez cet exemple de la construction d'un labyrinthe parfait dans la capsule sur la récursivité (mais avec un tracé à l'aide de la tortue python cette fois).
import random
import matplotlib.pyplot as plt
class Maillon:
def __init__(self, valeur, suivant=None):
self.valeur = valeur
self.suivant = suivant
class Pile:
def __init__(self):
self.taille = 0 # nombre d'assiettes dans la pile
self.sommet = None
def empiler(self, valeur):
self.sommet = Maillon(valeur, self.sommet)
self.taille += 1
def depiler(self):
if self.taille > 0:
valeur = self.sommet.valeur
self.sommet = self.sommet.suivant
self.taille -= 1
return valeur
def estVide(self):
return self.taille == 0
def lireSommet(self):
return self.sommet.valeur
# Dimensions de la grille:
LARGEUR = 20
HAUTEUR = 15
def voisinage(couple):
"""
Renvoie la liste des cellules voisines
de la cellule (ligne, colonne) = couple dans la grille.
"""
listeVoisins = []
i, j = couple[0], couple[1]
for d in (-1, 1):
if -1 < i+d < HAUTEUR: listeVoisins.append( (i+d, j) )
if -1 < j+d < LARGEUR: listeVoisins.append( (i, j+d) )
return listeVoisins
def dfs(s) :
P = {s: None}
Q = Pile()
Q.empiler(s)
while not(Q.estVide()) :
u = Q.lireSommet()
R=[y for y in voisinage(u) if y not in P]
if R :
v=random.choice(R)
P[v]=u
Q.empiler(v)
else :
Q.depiler()
return P
def dedale():
"""
Fonction dessinant le résultat
"""
labyrinthe = [ [0 for j in range(2*LARGEUR+1)] for i in range(2*HAUTEUR+1)]
parcours = dfs((0,0))
for i,j in parcours:
labyrinthe[2*i+1][2*j+1] = 1
if (i,j) != (0,0):
k,l = parcours[(i,j)]
labyrinthe[2*k+1][2*l+1] = 1
labyrinthe[i+k+1][j+l+1] = 1
labyrinthe[1][0] = 1
labyrinthe[2*HAUTEUR-1][2*LARGEUR] = 1
# le graphique:
plt.imshow(labyrinthe)
# on cache les graduations:
plt.xticks([])
plt.yticks([])
# on visualise le résultat:
plt.show()
dedale()
Exemple d'image obtenue:
