Parcours en profondeur

Parcours en profondeur#

Exercice

  1. Implantez l’algorithme de parcours en profondeur par une fonction récursive comme décrite sur la page Wikipedia.

from graph import Graph, Node, examples
from typing import List

def parcours_en_profondeur_recursif(G: Graph, u: Node) -> List[Node]:
    """
    INPUT:
    - 'G' - un graphe
    - 'u' - un sommet du graphe
    
    OUTPUT: La liste des sommets obtenus par un parcours en profondeur
    de `G` à partir de `u`.

    """
    ### BEGIN SOLUTION
    marked = set([])
    result = []  # Le parcours

    def explore(v):
        marked.add(v)
        result.append(v)
        for w in G.neighbors(v):
            if w not in marked:
                explore(w)

    explore(u)

    return result
    ### END SOLUTION

Exercice, suite

  1. Vérifiez votre implantation à l’aide des tests suivants:

import unittest
# Tests inspirés de:
# - https://sahandsaba.com/review-of-basic-algorithms-and-data-structures-in-python-graph-algorithms.html#depth-first-search-dfs
# - https://codereview.stackexchange.com/questions/153225/dfs-algorithm-unit-test
class DFSTest(unittest.TestCase):
    def test_single_vertex(self):
      graph = Graph([0])
      self.assertEqual(dfs(graph, 0), [0])
    
    def test_single_vertex_with_loop(self):
      graph = Graph([0], edges=[(0, 0, 1)])
      self.assertEqual(dfs(graph, 0), [0])
    
    def test_two_vertices_no_path(self):
      graph = Graph([0,1])
      self.assertEqual(dfs(graph, 0), [0])
      self.assertEqual(dfs(graph, 1), [1])
    
    def test_two_vertices_with_simple_path(self):
      graph = Graph([0,1], edges=[(0,1,1)], directed=True)
      self.assertEqual(dfs(graph, 0), [0, 1])
      self.assertEqual(dfs(graph, 1), [1])
    
    def test_complete_graph(self):
      for n in range(2, 10):
        graph = examples.complet(n)
        for v in range(n):
          self.assertEqual(set(dfs(graph, v)),  set(range(n)))
    
    def test_cycle_5(self):
        n = 5
        graph = examples.C5()
        for v in range(n):
            self.assertEqual(dfs(graph, v), list(range(v,n)) + list(range(0,v)))

    def test_(self):
        graph = Graph(["A", "B", "C", "D", "E", "F"],
                      edges=[("A", "B", 1), ("B", "C", 1), ("C", "D", 1),
                             ("A", "E", 1), ("E", "F", 1), ("F", "D", 1)],
                      directed=True
                     )
        self.assertEqual(dfs(graph, "A"), ["A", "B", "C", "D", "E", "F"])

dfs = parcours_en_profondeur_recursif
result = unittest.main(argv=[''], verbosity=0, exit=False).result
assert not result.failures, "Tous les tests ne sont pas passés"

Exercice, suite

  1. Reprenez l’algorithme de la feuille 01-ParcoursDeGraphe.md en utilisant une pile à la place d’une file pour todo.

def parcours_en_profondeur(G: Graph, u: Node) -> List[Node]:
    """
    INPUT:
    - 'G' - un graphe
    - 'u' - un sommet du graphe
    
    OUTPUT: un parcours en profondeur de `G`
    """
    ### BEGIN SOLUTION
    marked = {u} # L'ensemble des sommets déjà rencontrés
    todo   = [u] # L'ensemble des sommets déjà rencontrés, mais pas encore traités
    result = [] # Le parcours
    
    while todo:
        # Invariants:
        # - Si `v` est dans `marked`, alors il y a un chemin de `u` à `v`
        # - Si `v` est dans `marked` et pas dans `todo`
        #   alors tous les voisins de `v` sont dans dans `marked`
        v = todo.pop()
        result.append(v)
        for w in reversed(G.neighbors(v)):
            if w not in marked:
                marked.add(w)
                todo.append(w)
    return result
    ### END SOLUTION

Tests:

dfs = parcours_en_profondeur
result = unittest.main(argv=[''], verbosity=0, exit=False).result
assert not result.failures, "Tous les tests ne sont pas passés"