%% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %% > [!nav] > ↩ [[Code et Développement/Programmation/Graphes/Graphes|Accueil · Graphes]] > > | [[Code et Développement/Programmation/Graphes/03_Parcours en largeur (BFS)\|← Parcours en largeur – BFS]] | [[Code et Développement/Programmation/Graphes/05_Algorithme de Dijkstra\|Algorithme de Dijkstra →]] | > |:---|---:| %% nav-fin %% # Parcours en profondeur (DFS) Ce chapitre présente le **parcours en profondeur**, ou **DFS** pour *Depth First Search*. Il détermine tous les sommets que l'on peut atteindre depuis un sommet source. Le parcours en profondeur ne donne pas le plus court chemin. Pour cela, on utilise le [[Code et Développement/Programmation/Graphes/03_Parcours en largeur (BFS)|parcours en largeur]]. Le principe : depuis la source, on avance de voisin en voisin, tant qu'on trouve un sommet non découvert. Quand un sommet n'a plus de voisin non découvert, on revient au sommet précédent. Ce retour s'appelle le **retour arrière** (*backtrack*). Le parcours s'arrête quand on est revenu à la source et qu'elle n'a plus de voisin non découvert. ## La stratégie Le parcours utilise une [[Code et Développement/Programmation/Piles et Files/01_Les piles|pile]] : le dernier sommet entré est le premier sorti. Le sommet de la pile est le sommet où l'on se trouve. 1. On marque la source comme découverte et on l'empile. 2. On regarde le sommet u au sommet de la pile. 3. Si u a un voisin v non découvert, on marque v comme découvert, on note que son parent est u, et on empile v. 4. Sinon, on dépile u : c'est le retour arrière. 5. On recommence à l'étape 2 tant que la pile n'est pas vide. À chaque étape, on n'empile qu'un seul voisin. Les autres voisins de u seront examinés plus tard, au retour sur u. **À manipuler :** suivez le parcours depuis A. Les voisins sont pris dans l'ordre alphabétique. Observez les dépilements : chacun est un retour arrière. À la fin, le bouton « Arbre du parcours » ne garde que les arêtes de l'arbre. ```sq-graphe arêtes: A-B, B-F, C-D, C-E, C-F, D-E, F-G, F-A, G-D départ: A parcours: profondeur ``` ## Le programme Le graphe est le graphe de référence, stocké dans un dictionnaire (voir [[Code et Développement/Programmation/Graphes/02_Représentation en Python|Représentation en Python]]). ```python D = { 'A': {'B', 'F'}, 'B': {'A', 'F'}, 'C': {'D', 'E', 'F'}, 'D': {'C', 'E', 'G'}, 'E': {'C', 'D'}, 'F': {'A', 'B', 'C', 'G'}, 'G': {'D', 'F'}, } ``` ```python def dfs(G, s): parent = {s: None} # sommets découverts et leur parent pile = [s] while pile: u = pile[-1] # sommet de la pile non_decouverts = [v for v in sorted(G[u]) if v not in parent] if non_decouverts: v = non_decouverts[0] parent[v] = u pile.append(v) # on empile un seul voisin else: pile.pop() # retour arrière return parent print(dfs(D, 'A')) ``` Ce programme affiche : ``` {'A': None, 'B': 'A', 'F': 'B', 'C': 'F', 'D': 'C', 'E': 'D', 'G': 'D'} ``` Chaque sommet est associé au sommet depuis lequel il a été découvert. Le chemin de A vers E suivi par le parcours est A → B → F → C → D → E. Ce n'est pas le plus court : A → F → C → E compte une arête de moins. ## Version récursive Le parcours en profondeur s'écrit aussi de façon récursive (voir [[Code et Développement/Programmation/Récursivité/01_Cours Récursivité|Récursivité]]). La pile des appels de fonction joue alors le rôle de la pile. ```python def dfs_rec(G, s, parent=None): if parent is None: # premier appel : on crée le dictionnaire parent = {s: None} for v in sorted(G[s]): if v not in parent: parent[v] = s dfs_rec(G, v, parent) return parent print(dfs_rec(D, 'A')) ``` Ce programme affiche le même résultat que la version avec une pile. Le dictionnaire est créé dans la fonction, au premier appel. Il ne faut pas l'écrire comme valeur par défaut du paramètre, par exemple `def dfs_rec(G, s, parent={})`. Python crée cette valeur par défaut une seule fois, à la définition de la fonction. Un second appel de `dfs_rec` réutiliserait alors le dictionnaire du premier appel et renverrait un résultat faux. ## Arbre couvrant et connexité Les arêtes entre chaque sommet et son parent forment un arbre : l'**arbre du parcours en profondeur**. Si le parcours atteint tous les sommets, cet arbre est un arbre couvrant, et le graphe est connexe. Le parcours en profondeur sert donc à tester si un graphe est connexe. Pour voir cet arbre, déroulez le parcours de la section « La stratégie », puis cliquez sur « Arbre du parcours ». ## Détecter un cycle Le parcours en profondeur détecte aussi un cycle dans un graphe non orienté. Pendant le parcours, chaque voisin v du sommet courant u est dans l'un de ces cas : - v n'est pas découvert : l'arête u–v entre dans l'arbre du parcours ; - v est le parent de u : c'est l'arête par laquelle on est arrivé sur u ; - v est déjà découvert et n'est pas le parent de u : l'arête u–v ferme un cycle. ```python def a_un_cycle(G, s, parent=None): if parent is None: parent = {s: None} for v in sorted(G[s]): if v not in parent: parent[v] = s if a_un_cycle(G, v, parent): return True elif v != parent[s]: # déjà découvert, autre que le parent return True return False print(a_un_cycle(D, 'A')) T = { 'A': {'B'}, 'B': {'A', 'C', 'D'}, 'C': {'B'}, 'D': {'B'}, } print(a_un_cycle(T, 'A')) ``` Ce programme affiche : ``` True False ``` Le graphe de référence contient des cycles, par exemple A → B → F → A. Le graphe `T` est un arbre : il n'a aucun cycle. La fonction n'examine que les sommets atteints depuis `s`. Pour un graphe non connexe, on la lance depuis chaque sommet non encore découvert. **À manipuler :** un cycle du graphe est surligné. Cliquez sur des arêtes pour les retirer, jusqu'à ce qu'il ne reste aucun cycle. Le graphe devient alors un arbre. ```sq-graphe-proprietes arêtes: A-B, B-F, C-D, C-E, C-F, D-E, F-G, F-A, G-D ``` ## Avec networkx Le module `networkx` fournit le parcours en profondeur. `nx.dfs_tree` renvoie l'arbre du parcours. `nx.dfs_edges` renvoie ses arêtes, dans l'ordre de découverte. ```python import networkx as nx G = nx.Graph(D) print(list(nx.dfs_edges(G, 'A'))) ``` Ce programme affiche par exemple : ``` [('A', 'B'), ('B', 'F'), ('F', 'C'), ('C', 'D'), ('D', 'E'), ('D', 'G')] ``` L'ordre suit l'ordre des ensembles du dictionnaire : il peut varier d'une exécution à l'autre. ## Graphe orienté Le parcours en profondeur fonctionne aussi sur un graphe orienté. On ne suit alors que le sens des flèches. ```python D = { 'A': {'B'}, 'B': {'F'}, 'C': {'D', 'E', 'F'}, 'D': {'E'}, 'E': set(), 'F': {'A', 'G'}, 'G': {'D'}, } print(dfs(D, 'A')) ``` Ce programme affiche : ``` {'A': None, 'B': 'A', 'F': 'B', 'G': 'F', 'D': 'G', 'E': 'D'} ``` C n'est atteint par aucun chemin depuis A. Il n'apparaît pas dans le résultat. **À manipuler :** à la fin du parcours, C reste grisé. ```sq-graphe arêtes: A>B, B>F, C>D, C>E, C>F, D>E, F>G, F>A, G>D départ: A parcours: profondeur ``` %% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %% > [!nav] > ↩ [[Code et Développement/Programmation/Graphes/Graphes|Accueil · Graphes]] > > | [[Code et Développement/Programmation/Graphes/03_Parcours en largeur (BFS)\|← Parcours en largeur – BFS]] | [[Code et Développement/Programmation/Graphes/05_Algorithme de Dijkstra\|Algorithme de Dijkstra →]] | > |:---|---:| %% nav-fin %%