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: un parcours en profondeur de `G`
    """
    # VOTRE CODE ICI
    raise NotImplementedError()

Exercice, suite

2. 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

Exercice, suite

3. 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`
    """
    # VOTRE CODE ICI
    raise NotImplementedError()

Tests:

dfs = parcours_en_profondeur
result = unittest.main(argv=[''], verbosity=0, exit=False).result

assert not result.failures