Algorithme de parcours d'un graphe en profondeur
Algorithme
def parcours_rec_profondeur(g, noeud, liste_sommets_visites):
liste_sommets_visites.append(noeud)
for voisin in g.liste_voisins(noeud):
if voisin not in liste_sommets_visites:
parcours_rec_profondeur(g, voisin, liste_sommets_visites)Déroulement détaillé sur un exemple
Graphe
On choisi de parcourir le graphe à partir du nœud ① .
Déroulement détaillé
p_r_p avec nœud = 1 et l_s_v = []Ajout de ① dans l_s_v donc l_s_v vaut [1]
Boucle (🡆 ) avec les voisins de ① , c'est-à-dire ② et ③ :
🡆 Itération avec voisin = 2 :
2 n'est pas dans l_s_v donc :
p_r_p avec nœud = 2 et l_s_v = [1]Ajout de ② dans l_s_v donc l_s_v vaut [1,2]
Boucle (🡆 ) avec les voisins de ② , c'est-à-dire ④ , ⑤ :
🡆 Itération avec voisin = 4 :
4 n'est pas dans l_s_v donc :
p_r_p avec nœud = 4 et l_s_v = [1,2]Ajout de ④ dans l_s_v donc l_s_v vaut [1,2,4]
Boucle (🡆 ) avec les voisins de ④ , c'est-à-dire ⑤ :
🡆 Itération avec voisin = 5 :
p_r_p avec nœud = 5 et l_s_v = [1,2,4]Ajout de ⑤ dans l_s_v donc l_s_v vaut [1,2,4,5]
Boucle (🡆 ) avec les voisins de ⑤ , c'est-à-dire ① :
🡆 Itération avec voisin = 1 :
1 est déjà dans l_s_v, donc rien.
🡆 Fin de la boucle
🡆 Fin de la boucle
🡆 Itération avec voisin = 5
5 est déjà dans l_s_v donc rien.
🡆 Fin de la boucle
🡆 Itération avec voisin = 3
3 n'est pas dans l_s_v donc :
p_r_p avec nœud = 3 et l_s_v = [1,2,4,5]Ajout de ③ dans l_s_v donc l_s_v vaut [1,2,4,5,3]
Boucle (🡆 ) avec les voisins de ③ , c'est-à-dire ④ :
🡆 Itération avec voisin = 4 :
4 est déjà dans l_s_v, donc rien
🡆 Fin de la boucle
🡆 Fin de la boucle
