Parcourir le graphe à partir du sommet A¶
Parcours "libre"¶
on part de A:
on traite "A" (on n'a pas le choix ...)
on découvre "B" et "C" (opened)
on traite "C", (par exemple)
on traite "B" (pas le choix)
on traite "E" (par exemple)
on traite "D" (par exemple)
on traite "F" (pas le choix)
on traire "G" (pas le choix)
Il n'y a plus de sommets "opened" : c'est fini
NB : H n'a pas été traité (non accessible depuis A)
Arbre de parcours¶
Chaque sommet nouvellement traité peut être rattaché à un sommet déjà traité : on obtient un arbre de parcours
ici, si l'on a plusieurs possibilités, on prend le plus petit sommet (dans l'ordre alphabétique)
on va vers "B"
puis vers "D"
on est bloqué sur "D" ("A" déjà traité)
on revient sur "B" et on va en "E"
on va en "F"
puis en "G" "C"
on bloque en "C", on revient sur "F", on va en "G"
C'est fini ?
NON :
on revient sur "F", on revient sur "E", puis sur "B", puis sur "A" (et maintenant c'est fini !)
Un autre parcours en profondeur :
Parcours "en largeur (d'abord)"¶
On avance en cercles concentrique autour de $s_0$ :
- $s_0$ (distance 0)
- les voisins de $s_0$ (distance 1)
- les voisins des voisins qui n'ont pas été traités (distance 2)
- ...
NB : distance entre $s_0$ et $s$ : la longueur du plus court chemin
distance 0
distance 1
NB : peu importe l'odre de traitement des sommets à la même distance de $s_0$
distance 2
distance 3
distance 4
distance 5
distance 6
...
Parcours "au meilleur choix"¶
On peut disposer d'un critère précis pour choisir le prochain sommet à traiter
exemple : on traite en priorité le sommet le plus proche du sommet B (en distance euclidienne)
ainsi de suite ...
Peut permettre de trouver rapidement un chemin vers un sommet cible (cf algorithme A* (MPI))