CommencerCommencez gratuitement

Implémenter DFS pour les graphes

Dans cet exercice, vous allez implémenter un algorithme de parcours en profondeur (depth first search) pour parcourir un graphe.

Rappelez-vous les étapes :

  1. Commencez à n'importe quel sommet
  2. Ajoutez le sommet à la liste des sommets visités
  3. Pour chaque sommet adjacent du nœud courant
  • S'il a déjà été visité -> l'ignorer
  • S'il n'a pas été visité -> effectuer récursivement DFS

Pour vous aider à tester votre code, le graphe suivant a été chargé à l'aide d'un dictionnaire.

Graphical representation of a graph.

graph = {
  '0' : ['1','2'],
  '1' : ['0', '2', '3'],
  '2' : ['0', '1', '4'],
  '3' : ['1', '4'],
  '4' : ['2', '3']
}

Cet exercice fait partie du cours

<cours>Structures de données et algorithmes en Python</cours>
Voir le cours

Instructions de l’exercice

  • Vérifiez que current_vertex n'a pas encore été visité.
  • Ajoutez current_vertex à visited_vertices.
  • Appelez dfs() de manière récursive en lui passant les valeurs appropriées.

Exercice interactif pratique

Essayez cet exercice en complétant ce code d’exemple.

def dfs(visited_vertices, graph, current_vertex):
    # Check if current_vertex hasn't been visited yet
    if current_vertex not in ____:
        print(current_vertex)
        # Add current_vertex to visited_vertices
        ____.add(____)
        for adjacent_vertex in graph[current_vertex]:
            # Call recursively with the appropriate values
            ____(____, ____, ____)
            
dfs(set(), graph, '0')
Modifier et exécuter le code