Parcours en profondeur
Le parcours en profondeur d'un graphe : version récursive et version à pile, ordres de découverte et de fin, arbre de parcours, retour en arrière, détection d'un cycle et coût en O(n + m).
- 25 cartes
- 5 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
- Comprendre
Quelques cartes du deck
Ordre de découverte : de quoi s'agit-il ?
Voir la réponse
Ordre dans lequel les sommets sont atteints pour la première fois, avant que leurs voisins soient explorés.
Il dépend de l'ordre dans lequel on lit les voisins : avec l'ordre alphabétique, on prend le premier voisin non visité et on s'enfonce.
Graphe de 7 sommets, arêtes : A-B, A-C, B-D, B-E, C-F, E-G, F-G. Parcours en profondeur récursif depuis A, voisins dans l'ordre alphabétique. Quel est l'ordre de découverte ?
- A B D E G F C
- A B C D E F G
- A C F G E B D
- A B D E C F G
Voir la réponse
A B D E G F C
A, puis B (premier voisin), D (impasse : retour à B), E, G, puis F (voisin de G), puis C. A B C D E F G est l'ordre en largeur, A C F G E B D celui d'une version à pile qui empile les voisins dans l'ordre alphabétique, et A B D E C F G oublie que F et C sont atteints par G avant le retour à A.
La version itérative du parcours en profondeur remplace la récursivité par une … explicite ; le parcours en largeur utilise une ….
Voir la réponse
La version itérative du parcours en profondeur remplace la récursivité par une pile explicite ; le parcours en largeur utilise une file.
Une pile reprend toujours le dernier élément ajouté, comme un appel récursif revient au dernier appel ouvert.
Ordre de fin : de quoi s'agit-il ?
Voir la réponse
Ordre dans lequel les sommets sont terminés : un sommet est fini quand tous ses voisins ont été explorés.
La source est toujours la dernière à finir. Cet ordre sert au tri topologique et à la détection des composantes fortement connexes.