Parcours de graphe

Algorithmes de référence : Parcours de graphe

Définitions et notations :
Pour un graphe orienté, chaque arête (arc) est un couple (x,y)∈E, où y est un successeur de x. Dans un graphe non orienté, chaque arête est une paire {x,y} où x et y sont voisins (x est un successeur de y et y est un successeur de x. Dans les deux cas l'arête (arc) est dénotée xy.
On représente généralement l'ensemble E des arêtes d'un graphe
– soit par une matrice booléenne M telle que M[x,y]=1 ssi xy∈E,
– soit par un tableau Succ (pour un graphe orienté, Adj pour un graphe non orienté) de listes de successeurs (ou d'adjacence) tel que Succ[x] (ou Adj[x]) contient la liste des successeurs (ou voisins) de x.
Avec n=|V| et m=|E|, la taille de M est n² et la taille de Succ est m. Un algorithme de graphe qui a une complexité en O(n²) ou en O(n+m) est dit linéaire sur la taille du graphe.
L'algorithme Degré ci-dessous a une complexité linéaire.

algorithme Degré
Donnée : un graphe orienté G=(V,Succ).
Résultat : les degrés entrant D− et sortant D+ de chaque sommet, càd leurs nombres de prédécesseurs et de successeurs.
Initialement : D−[x]=D+[x]=0 pour chaque x∈V.

Pour x∈V faire

Pour y∈Succ(x) faire

D−[y]← D−[y]+1;
D+[x]← D+[x]+1;

schéma algorithmique PARCOURS
Donnée : Un graphe orienté G=(V,E), un sommet x_o de G.
Résultat : l'ensemble Atteint contient l'ensemble des descendants de x₀ dans G.

Atteint← {x_o};
Exploré← ∅;
Tantque Atteint−Exploré ≠ ∅ faire

CHOISIR x dans Atteint−Exploré;
Si tous les successeurs de x sont dans Atteint

alors

Exploré← Exploré∪{x};

sinon

CHOISIR un successeur y de x (càd xy∈E) qui n'est pas dans Atteint;
Atteint← Atteint∪{y};

Invariants : x∈Atteint. Exploré⊆Atteint. On n'atteint que des descendants de x_o. Les successeurs d'un sommet exploré sont atteints.

Ce schéma algorithmique est réalisé différemment selon la manière dont se fait le choix d'un sommet par la fonction CHOISIR dans Atteint−Exploré. Concrètement, on va utiliser soit une file (premier entré - premier sorti) pour avoir un parcours en largeur, soit une pile (dernier entré - premier sorti) pour avoir un parcours en profondeur.

algorithme LARGEUR
Donnée : Un graphe orienté G=(V,E), un sommet x_o de G.
Résultat : un parcours en largeur (=concentrique) de G à partir de x₀.
Initialement : la file F est vide. Pour chaque sommet i, dist[i]=∞. AR=∅.

Enfiler(F,x_o);
Atteint← {x_o};
dist[x_o]← 0; Répéter

x← Défiler(F);
Pourchaque successeur y de x qui n'est pas déjà dans Atteint faire

Enfiler(F,y);
Atteint← Atteint∪{y};
dist[y]=dist[x]+1;
AR← AR∪{xy};

jusqu'à estvide(F);

Théorèmes :
– Les sommets sont atteints dans l'ordre de leur plus courte distance à x_o (tableau dist).
– A un parcours en largeur est associée une arborescence dite concentrique (dont les sommets sont dans Atteint et les arêtes dans AR).
– LARGEUR donne tous les plus courts chemins entre x_o et chacun de ses descendants dans G .
– Si tous les sommets du graphe sont atteints par le parcours, on construit une arborescence, de racine x_o, dite arborescence recouvrante de G.

Preuve d'arrêt : Un sommet est placé au plus une fois dans la file, il y aura donc au plus n sommets dans la file. Chaque tour du Répéter enlève un élément de la file, donc cette boucle aura au plus n tours.

Preuve de résultat : Par induction sur le nombre de tours du répéter, on montre que "Atteint ne contient que des descendants de x_o" est un invariant et que l'algorithme continue tant qu'il reste un descendant de x_o qui n'est pas encore atteint (induction sur la longueur du chemin entre x_o et chacun de ses descendants.

Complexité : linéaire dans la taille du graphe.

algorithme PROFONDEUR
// version itérative
Donnée : Un graphe orienté G=(V,E), un sommet x_o de G.
Résultat : un parcours en profondeur de G à partir de x₀.
Initialement : la pile P est vide. Atteint=∅. i=j=0. AR=∅.

Empiler(P,x_o);
Atteint← {x_o};
Répéter

x← Dépiler(P);
Pourchaque successeur y de x qui n'est pas déjà dans Atteint faire

Empiler(P,y);
Atteint← Atteint∪{y};
AR← AR∪{xy};

jusqu'à estvide(P);

fonction PROFONDEUR(x,i,j,Atteint)
// version récursive
Donnée : Un graphe orienté G=(V,E), un sommet x_o de G.
Résultat : un parcours en profondeur de G à partir de x₀.
N.B. C'est ici la piile de récursivité qui gère le parcours.
Appel initial : PROFONDEUR(x_o,0,0,∅).

i← i+1; Prefixe[x]=i;
Atteint← Atteint∪{x};
Pourchaque y successeur de x n'appartenant pas à Atteint faire

PROFONDEUR(y,i,j,Atteint);

j← j+1; Postfixe[x]=j.

Théorèmes :
– A un parcours en profondeur est associée une arborescence, dont les sommets sont dans Atteint et les arêtes dans AR.
– Une arête xy de G appartient à AR ssi Prefixe[y]−Prefixe[x]=1 et Postfixe[x]>Postfixe[y].
– Quand Prefixe[z]−Prefixe[x]>1 et Postfixe[x]>Postfixe[z], xz est un arc de transitivité car il existe un chemin x...y..z avec x y et z tous différents dans AR.
– Quand Prefixe[x]>Prefixe[y] et Postfixe[x]<Postfixe[y], l'arc xy est un arc retour car yx soit appartient à AR soit est une arête de transitivité.
– Quand Prefixe[x]>Prefixe[y] et Postfixe[x]>Postfixe[y], l'arc xy est un arc traversier qui n'appartient pas à AR. Tous les arcs traversiers vont "de droite à gauche" càd d'un sommet vers un sommet atteint auparavant.

Preuve d'arrêt : Il y a au plus un appel récursif par descendant de x_o et au plus n−1 descendants de x_o.

Preuve de résultat : Par induction sur le nombre d'appels récursifs, on démontre que Atteint ne contient que des descendants de x_o (invariant). Par induction sur la longueur d'un chemin entre x_o et chacun de ses descendants atteints, on démontre que tous les descendants sont atteints.

Complexité : linéaire dans la taille du graphe.

schéma algorithmique EXPLORER
Donnée : Un graphe orienté G=(V,E).
Résultat : Tous les sommets du graphe sont atteints. Formation d'une forêt (suite d'arborescences).

Atteint←∅;
Tantque V−Atteint≠∅ faire

CHOISIR x dans V−Atteint;
// Sans réinitialiser Atteint ni les compteurs Prefixe et Postfixe :
Parcours(G,x).

Théorème : La propriété des arcs traversiers est conservée pour les arcs entre les arborescences successives de la forêt obtenue.

Complexité linéaire.

N.B. Page inspirée du cours d'algorithmique de licence de J-P. Bordat (université de Montpellier, 1992-1995).