Présentation du parcours
Un parcours en profondeur permet de trouver tous les sommets atteignables depuis un sommet initial u, c’est-à-dire l’ensemble des sommets v pour lesquels il existe une marche menant de u à v.
L’idée est simple : à partir d’un sommet initial, on explore une mnarche aussi longtemps que possible sans jamais passer deux fois par le même sommet. Lorsqu’on est bloqué, on revient en arrière sommet par sommet jusqu’à trouver un voisin non visité. On explore alors une marche dans cette direction jusqu’à être bloqué à nouveau etc.
Attention : Ce parcours se fait sur le graphe, c’est à dire que dans PyRat, le pion ne bouge pas. Le parcours en profondeur renverra une marche finale, qui elle sera appliquée sous forme de mouvements.
Voici un programme Python (donné sous sa forme récursive) implémentant un parcours en profondeur de graphe :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
def depthFirstSearch (graph, sourceNode) : # Variable storing the visited nodes not to go there again visited = [] # Locally defined recursive function (to see "visited" as global) # It prints to stdout the nodes where it goes def depthFirstSearchRecursive (graph, currentNode) : # First we say we visit currentNode visited.append(currentNode) print(currentNode) # We visit all non-visited neighbors of currentNode for neighbor in graph[currentNode] : if neighbor not in visited : depthFirstSearchRecursive(graph, neighbor) print("back") # First call depthFirstSearchRecursive(graph, sourceNode) ################################################################### # Test graph 1 graph1 = [[1, 2, 5], [0, 2, 5], [0, 1], [4, 5], [3, 5], [0, 1, 3, 4]] depthFirstSearch(graph1, 0) print("") # Test graph 2 graph2 = [[5, 1, 2], [2, 0, 5], [0, 1], [5, 4], [3, 5], [4, 3, 1, 0]] depthFirstSearch(graph2, 0) |
Dans cet exemple, le graphe utilisé est le suivant, où le sommet source est 0 (représenté sous forme d’un tableau de listes) :
Si vous exécutez ce code, vous verrez que le résultat n’est pas dans le même ordre pour les deux graphes testés, qui sont pourtant identiques (seul change l’ordre dans lequel sont listés les voisins des sommets).
Retrouver le chemin à partir du parcours
Pour retrouver la marche ayant conduit du sommet initial au sommet visité, on peut modifier l’algorithme ainsi :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
def depthFirstSearch (graph, sourceNode) : # Variable storing the visited nodes not to go there again visited = [] # Locally defined recursive function # The arguments to function depthFirstSearchRecursive are a graph to explore and a currentNode # It prints to stdout the nodes where it goes and the path to it # Here, we also have a "path" parameter, to show the sequence of nodes until the current node is reached def depthFirstSearchRecursive (graph, currentNode, path) : # First we say we visit currentNode visited.append(currentNode) print(currentNode, "path :", repr(path)) # We visit all neighbors of currentNode for neighbor in graph[currentNode] : if neighbor not in visited : depthFirstSearchRecursive(graph, neighbor, path + [neighbor]) print("back") # First call depthFirstSearchRecursive(graph, sourceNode, [sourceNode]) ################################################################### # Test graph 1 graph1 = [[1, 2, 5], [0, 2, 5], [0, 1], [4, 5], [3, 5], [0, 1, 3, 4]] depthFirstSearch(graph1, 0) print("") # Test graph 2 graph2 = [[5, 1, 2], [2, 0, 5], [0, 1], [5, 4], [3, 5], [4, 3, 1, 0]] depthFirstSearch(graph2, 0) |
À noter que les marches trouvées n’ont aucune raison d’être les plus courtes possibles.
Propriétés de l’algorithme
Terminaison
Puisque chaque sommet du graphe ne peut être visité qu’une fois, l’algorithme termine.
Correction
L’algorithme du parcours en profondeur est tel qu’il va visiter l’ensemble des sommets atteignables à partir de u.
Pour vérifier cette propriété, on remarque d’abord que l’ensemble des sommets visités par le parcours en profondeur sont en effet atteignables : cela se prouve par récurrence très simplement (u est trivialement atteignable depuis u puis des voisins de sommets atteignables sont eux-mêmes atteignables).
Ensuite il faut vérifier que tous les sommets atteignables sont visités par le parcours en profondeur. Procédons par l’absurde : un sommet atteignable v par définition est tel qu’il existe un chemin y menant depuis u. On regarde sur un tel chemin l’avant dernier sommet. Cet avant dernier sommet n’a pas été visité sinon v aurait été visité. Par récurrence, on en déduit que u n’a pas été visité. Contradiction.
Complexité
Le parcours ne consulte que deux fois chaque arête, avec un nombre d’opérations élémentaires proportionnel à cette quantité. On en déduit que la complexité est en O(|E|).
Des parcours en profondeur
Le parcours en profondeur dont il est question dans le cours n’autorise de visiter chaque sommet du graphe qu’une fois, il permet donc de découvrir l’ensemble des sommets atteignables.
Une autre utilité aux parcours en profondeur est de lister l’ensemble des chemins élémentaires depuis un sommet initial u. Il suffit alors pour cela de modifier l’algorithme de la façon suivante :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
def depthFirstSearchRecursive (graph, currentNode, visited) : # We print the current path print(repr(visited)) # We visit all neighbors of currentNode that are not visited in the current path for neighbor in graph[currentNode] : if neighbor not in visited : depthFirstSearchRecursive(graph, neighbor, visited + [neighbor]) ################################################################### def depthFirstSearch (graph, sourceNode) : depthFirstSearchRecursive(graph, sourceNode, []) ################################################################### # Test graph graph = [[1, 2, 5], [0, 2, 5], [0, 1], [4, 5], [3, 5], [0, 1, 3, 4]] depthFirstSearch(graph, 0) |
Cet algorithme sera très utile lorsque l’on travaillera sur l’algorithme de backtracking.