Recherche en profondeur (Depth-First Search)

- Un parcours en profondeur d’un graphe G:

  • Visite tous les sommets et toutes les arêtes de G,
  • Détermine si G est connexe ou non,
  • Calcule les composantes connexes de G,
  • Calcule une forêt couvrante pour G.

- La complexité en temps d’un parcours en profondeur est O(n+m).

- L’algorithme de parcours en profondeur peut être modifié pour résoudre d’autres problèmes sur les graphes:

  • trouver et retourner un chemin entre deux sommets,
  • trouver un cycle dans un graphe.

de: http://www.iro.umontreal.ca/~hamelsyl/recherche.pdf

Modifié le: lundi 7 juillet 2014, 22:25