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.
Modifié le: lundi 7 juillet 2014, 22:25