Comment éviter de visiter deux fois un sommet pendant un parcours de graphe ?
Réponse courte
En parcours en largeur, marque chaque sommet dès son ajout à la file ; en parcours en profondeur récursif, marque-le dès l’entrée dans l’appel. N’explore ensuite que les sommets qui ne sont pas encore marqués.
Comprendre
Marquer au moment de la découverte
Un ensemble visited conserve les sommets déjà découverts. En parcours en largeur, ajoute le sommet de départ dans visited dès sa mise en file. Quand un voisin est encore absent de l’ensemble, ajoute-le immédiatement, mémorise sa distance et son prédécesseur, puis enfile-le. Ainsi, un autre chemin qui mène au même voisin le reconnaît comme déjà connu.
Pourquoi ne pas attendre son traitement ?
Dans un triangle A–B–C–A, depuis A, le parcours découvre B et C. Lorsque B examine ses voisins, il voit C. Si C n’a été marqué qu’au moment où il sera retiré de la file, il peut être ajouté une seconde fois alors qu’il attend déjà. Le marquer à l’enfilage empêche ce doublon. Être découvert signifie qu’il figure déjà parmi les connaissances du parcours ; être traité signifie que ses voisins ont été examinés.
Partager le même état
En profondeur récursive, partage le même ensemble entre les appels et marque le sommet à l’entrée de la fonction. Ne crée pas un nouvel ensemble pour chaque appel, sinon chaque branche oublie les sommets trouvés par les autres. Dans un graphe non connexe, recommence depuis un sommet encore absent si tu veux explorer toutes les composantes.
Étapes
- Crée un ensemble découvert et ajoute-y le sommet de départ avant la première exploration.
- Pour chaque voisin, vérifie qu’il n’est pas déjà dans l’ensemble.
- Marque-le immédiatement avant de l’ajouter à la file ou de lancer l’appel récursif.
- Partage le même ensemble pendant toute l’exploration ; pour couvrir un graphe non connexe, lance un parcours depuis chaque sommet encore absent.
Exemples
- Dans le triangle A–B–C–A, le départ A découvre B et C ; quand B examine C, l’ensemble contient déjà C, donc il ne l’enfile pas à nouveau.
- Dans la largeur du graphe A–B, A–C, B–D, C–D, le premier chemin qui découvre D l’ajoute une fois à la file ; l’autre voisin le trouve déjà marqué.
- Pour un sommet isolé Z, l’ensemble contient Z après son ajout initial, et le parcours se termine sans voisin à examiner.
Pièges fréquents
- Marquer un sommet seulement quand on le retire de la file laisse une fenêtre pendant laquelle plusieurs voisins peuvent l’y ajouter.
- Créer un nouvel ensemble visited dans chaque appel récursif ne partage pas l’historique commun et peut provoquer des revisites ou une récursion sans fin sur un cycle.
Pourquoi ça marche
L’ensemble sert à la fois de mémoire des sommets déjà découverts et de filtre avant toute nouvelle insertion dans la structure d’attente.
