Graphes et optimisation

Accueil > Cours > Parcours des graphes

Parcours des graphes

mardi 16 août 2005, par

Parcours des arborescences en largeur

Le parcours en largeur (breadth-first search) d’une arborescence consiste à visiter les nœuds dans l’ordre « de gauche à droite et de haut en bas » :

parcourir une arborescence en largeur :
enfiler la racine;
TANT QUE la file n'est pas vide
soit n le premier noeud de la file;
{ traitement de n}
défiler;
enfiler tous les fils de n
FIN TANT QUE
Figure 14

Figure 14.Ordre de parcours en largeur : 1, 2, 3, 4, 5, 6, 7

Parcours des arborescences en profondeur

Le parcours récursif en profondeur (depth-first search) d’une arborescence consiste à visiter la racine, la visite d’un nœud étant terminée lorsqu’on a visité tous ses fils :

parcourir une arborescence en profondeur :
visiter la racine
visiter un noeud n:
{ pré-traitement de n}
visiter tous les fils de n
{ post-traitement de n}

L’ordre de visite est « de haut en bas et de gauche à droite »(ordre préfixe).
L’ordre de post-visite est « de bas en haut et de gauche à droite »(ordre postfixe).

Figure 15

Figure 15.Ordre de visite : 1, 2, 5, 6, 3, 4, 7 ; de post-visite : 5, 6, 2, 3, 7, 4, 1

On peut effectuer un parcours en profondeur non récursif en marquant les nuds en cours de traitement, et en utilisant une pile pour garder la trace des nuds en attente :

parcourir une arborescence en profondeur :
empiler la racine;
TANT QUE la pile n'est pas vide
soit n le sommet de pile;
        SI n n'a pas été marqué ALORS
                { pré-traitement de n}
                marquer s;
                SI n a des fils ALORS
                        empiler le fils aîné de n
                FIN SI
        SINON
                { post-traitement de n}
                dépiler;
                SI n a des frères plus jeunes ALORS
                        empiler le frère cadet de n
                FIN SI
        FIN SI
FIN TANT QUE

Parcours de graphes

Les algorithmes de parcours des arborescences s’adaptent aux graphes, en considérant que l’on parcourt des arborescences associées aux sommets du graphe ; l’arborescence associée à un sommet est celle des descendants de ce sommet que l’on n’a pas encore parcourus. Les arbres sous-jacents à ces arborescences forment une forêt recouvrante du graphe (contenant tous les sommets du graphe)

Les ordres de parcours dépendent évidemment de l’ordre des sommets et de l’ordre des successeurs de chaque sommet (ordres implicites dans la représentation du graphe en mémoire).

Parcours en largeur

Figure 16

Figure 16.Ordre de parcours : 1, 2, 4, 5, 3

parcourir un graphe en largeur :
visiter tous les sommets
visiter un sommet s:
SI s n'a pas été marqué ALORS
        marquer et enfiler s;
        TANT QUE la file n'est pas vide
                soit n le premier sommet de la file;
                { traitement de n}
                défiler;
                marquer et enfiler tous les successeurs non marqués de n
        FIN TANT QUE
FIN SI

Preuve du programme : chaque sommet est visité, donc traité au moins une fois ; or, on ne peut enfiler que des sommets non encore traités ; par conséquent, chaque sommet est enfilé exactement 1 fois.

À chaque passage dans la boucle TANT QUE, on défile un sommet différent, donc chaque procédure visiter se termine. À la sortie de visiter, la file est vide ; donc chaque sommet aura été défilé, et par conséquent traité, exactement 1 fois.

Complexité : Chaque sommet est traité 1 fois, et chaque arc est examiné 1 fois (lors du traitement de son origine). La complexité est donc de l’ordre de .

Parcours en profondeur (récursif)

Figure 17

Figure 17.Ordre de visite : 1, 2, 4, 3, 5 ; de post-visite : 1, 5, 3, 4, 2

parcourir un graphe en profondeur :
visiter tous les sommets
visiter un sommet s:
SI s n'a pas encore été visité ALORS
        { pré-traitement de s}
        visiter tous les successeurs de s
        { post-traitement de s}
FIN SI

Preuve du programme : chaque sommet est visité exactement 1 fois.
Complexité : chaque sommet est visité 1 fois, chaque arc d’origine est examiné 1 fois. La complexité est donc de l’ordre de max (|A|,|S|).