Parcours en profondeur

Graphes • Exercices 1A

1

Indice

Utiliser la liste OCaml comme une pile pour gérer l'ordre de visite et marquer les sommets déjà rencontrés.

Écrire une fonction dfs_pile : int list array -> int -> int list qui renvoie l'ordre de visite des sommets d'un graphe sous la forme de listes d'adjacence per parcours en profondeur en utilisant une pile. La pile est une simple liste OCaml. On suppose le graphe connexe et le sommet de départ est donné en second paramètre.
2

Indice

Définir une fonction récursive qui marque les sommets déjà vus et accumule les résultats dans une liste avant de l'inverser.

Écrire une fonction dfs : int list array -> int list qui renvoie l'ordre de visite des sommets par parcours en profondeur récursif. On utilisera une fonction interne récursive qui explorera en profondeur chaque sommet. Cette deuxième version fonctionne même si le graphe n'est pas connexe.

flowchart TD Start([Début : dfs graphe]) --> Init["Soit n l'ordre du graphe
let deja_visites = [|false, ..., false|]
let parcours = ref []"] Init --> Loop_Init["Lancer l'exploration pour chaque sommet s
s = 0"] Loop_Init --> Cond_i{s < n ?} Cond_i -->|Vrai| Call_Explorer["Appeler la fonction d'exploration récursive :
explorer s"] Call_Explorer --> Inc_i["s = s + 1"] Inc_i --> Cond_i Cond_i -->|Faux| Reverse["Renverser la liste parcours accumulée"] Reverse --> End([Fin : Retourner parcours])

flowchart TD Start([Début : explorer sommet]) --> Cond_Visited{"sommet visité ?"} Cond_Visited -->|Vrai| End_Exp(["Fin de l'appel"]) Cond_Visited -->|Faux| Mark_Visited["Marquer sommet visité"] Mark_Visited --> Add_Parcours["Ajouter sommet au parcours"] Add_Parcours --> Init_Iter["Parcourir les voisins v de sommet"] Init_Iter --> Cond_Voisins{"Reste-t-il un voisin v
de sommet ?"} Cond_Voisins -->|Vrai| Rec_Call["Appel récursif :
explorer v"] Rec_Call --> Next_Voisin["Passer au voisin suivant v"] Next_Voisin --> Cond_Voisins Cond_Voisins -->|Faux| End_Exp