1. Apprendre
    2. /
  2. Cours
    3. /
  3. Structures de données et algorithmes en Python
Connected

Exercice

Implémenter une recherche en profondeur (DFS) pour les graphes

Dans cet exercice, vous allez implémenter un algorithme de recherche en profondeur afin de parcourir un graphe.

Rappelez-vous les étapes :

  1. Partir de n'importe quel sommet
  2. Ajouter 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 la DFS

Pour vous aider à tester votre code, le graphe suivant a été chargé au moyen 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']
}

Instructions

100 XP
  • Vérifiez si current_vertex n'a pas encore été visité.
  • Ajoutez current_vertex à visited_vertices.
  • Appelez dfs() de façon récursive en lui transmettant les valeurs appropriées.