Parcours de graphes

Algorithmique - L3

Fran¸cois Laroussinie

2 novembre 2010

Parcours de graphes

Proc´edureParcours(G)

//G= (S,A) begin pour chaquex?SfaireCouleur[x] := blanc

Choisirs?S

Couleur[s] := gris

r´ep´eter

Choisirxtq Couleur[x] = gris

pour chaque(x,y)?Afaire siCouleur[y] =blancalorsCouleur[y] := gris

Couleur[x] := noir

jusqu"`a?x.Couleur[x]?=gris; end

Parcours

Id´ees :

Onchoisit un sommetsdont tous les successeurs n"ont pas encore ´et´e d´ecouverts.

On explore les transitions issues deset on

cherche des successeurs despas encore d´ecouverts

Parcours

Id´ees :

Onchoisit un sommetsdont tous les successeurs n"ont pas encore ´et´e d´ecouverts.

On explore les transitions issues deset on

cherche des successeurs despas encore d´ecouverts

Trois ´etats pour les sommets :

non d´ecouvert,

d´ecouvert mais certains successeurs restent non d´ecouverts, ou

d´ecouvert ainsi que ses successeurs.

→trois couleurs (blanc/gris/noir). Plan

1D´efinitions

2Parcours en largeur

3Parcours en profondeur

4Extension lin´eaire

Plan

1D´efinitions

2Parcours en largeur

3Parcours en profondeur

4Extension lin´eaire

Parcours en largeur

on consid`ere un graphe non orient´e.

Arborescence de parcours

Pour chaque sommet, on va garder en m´emoire

par quelle arˆete il a

´et´e d´ecouvert

, c.-`a-d. depuis quel sommet...

Arborescence de parcours

Pour chaque sommet, on va garder en m´emoire

par quelle arˆete il a

´et´e d´ecouvert

, c.-`a-d. depuis quel sommet...

Π :S→S? {nil}

Π(u) =vssi

ua ´et´e d´ecouvert depuisv.

Arborescence de parcours

Pour chaque sommet, on va garder en m´emoire

par quelle arˆete il a

´et´e d´ecouvert

, c.-`a-d. depuis quel sommet...

Π :S→S? {nil}

Π(u) =vssi

ua ´et´e d´ecouvert depuisv. On construit donc un arbreGΠ= (S,AΠ) de racines. A

Πdef={(Π(v),v)|Π(v)?= nil}

Propri´et´e du parcours en largeur

L"algorithme va parcourir les sommets accessibles depuissen commen¸cant par ceux situ´es `a la distance 1, puis ceux situ´es `a la distance 2,etc.

Propri´et´e du parcours en largeur

L"algorithme va parcourir les sommets accessibles depuissen commen¸cant par ceux situ´es `a la distance 1, puis ceux situ´es `a la distance 2,etc.

De plus, l"algorithme va

1calculer ladistance minimalede chaque sommet `a l"origines,

2les chemins dansGΠseront desplus courts cheminsdeG.

Parcours en largeur deG= (S,A) non-orient´e

Proc´edurePL(G,s)

pour chaquex?S\{s}faire Couleur[x] := blanc; Π[x] := nil; Dist[x] :=∞;

Couleur[s] := gris; Π(s) := nil; Dist[s] := 0;

F:= File vide

Ajouter(F,s)

tant queF?=∅faire x:= ExtraireTˆete(F); pour chaque(x,y)?Afaire siCouleur[y] =blancalors

Couleur[y] := gris;

Dist[y] := Dist[x] + 1;

Π[y] :=x;

Ajouter(F,y);

Couleur[x] := noir

Parcours en largeur

Le sens du coloriage blanc/gris/noir est :

blanc: les sommetspas encore d´ecouverts

(et `a l"initialisation, saufs). gris: les sommetsd´ej`a d´ecouvertset dont lessuccesseurs imm´ediats n"ontpasencore ´et´etousd´ecouverts; noir: les sommets d´ecouverts donttous les successeurs imm´ediats ont aussi ´et´e d´ecouverts.

Terminaison et complexit´e

Tout ajout deudansF...

est conditionn´e par?Couleur[u] = blanc?, et

est suivi par un coloriage en gris deu.

Un sommet n"est colori´e en blanc qu"`a l"initialisation.

Terminaison et complexit´e

Tout ajout deudansF...

est conditionn´e par?Couleur[u] = blanc?, et

est suivi par un coloriage en gris deu.

Un sommet n"est colori´e en blanc qu"`a l"initialisation. ?une peut ˆetre ajout´e (et extrait) qu"au plus une fois. ?l"algorithme termine!

Terminaison et complexit´e

Tout ajout deudansF...

est conditionn´e par?Couleur[u] = blanc?, et

est suivi par un coloriage en gris deu.

Un sommet n"est colori´e en blanc qu"`a l"initialisation. ?une peut ˆetre ajout´e (et extrait) qu"au plus une fois. ?l"algorithme termine! Et sa liste d"adjacence n"est parcourue qu"au plus une fois.

Terminaison et complexit´e

Tout ajout deudansF...

est conditionn´e par?Couleur[u] = blanc?, et

est suivi par un coloriage en gris deu.

de la boucle principale :O(|A|);

de l"initialisation :O(|S|).

?Complexit´e enO(|S|+|A|) ouO(|G|)

Correction du parcours en largeur

Th´eor`emeSoientG= (S,A) un graphe non-orient´e ets?Sun sommet. L"algorithmePL(G,s) :

1d´ecouvre tous les sommets atteignables depuisset

uniquement eux;

2termine avec Dist[v] =δ(s,v) pour toutv?S;

3construit la table Π de telle sorte que pour tout sommetu?=s

atteignable depuiss, il existe un plus court chemin des`au dansGdont la derni`ere transition est (Π(u),u). NB :δ(s,v)def= longueur d"un plus court chemin entresetv

Propri´et´es - distances

D´efinitionG= (S,A),u,v?S

δ(u,v)def=?

min{p|u→pv}siu→?v ∞sinon Propri´et´e 13Soientu,v?Stels que (u,v)?A, alors on a :

Propri´et´es - parcours en largeur

Propri´et´e 14A tout moment de l"algorithme, on a pour tout sommetu: Dist[u]≥δ(s,u). Propri´et´e 15Lors de l"ex´ecution dePLsurG= (S,A) depuiss, `achaque ´etape de l"algorithme, si le contenu deFest de la forme [v1,v2,...,vk] o`uv1d´esigne l"´el´ement le plus ancien etvkle plus r´ecent, alors on a : Plan

1D´efinitions

2Parcours en largeur

3Parcours en profondeur

4Extension lin´eaire

Id´ee g´en´erale

On consid`ere des graphes orient´es.

Ici on choisitle sommet gris d´ecouvert le plus r´ecemment.

Au lieu d"une

file, on utilise unepile.

Id´ee g´en´erale

On consid`ere des graphes orient´es.

Ici on choisitle sommet gris d´ecouvert le plus r´ecemment.

Au lieu d"une

file, on utilise unepile. On d´eroule donc un chemin (gris) le plus loin possible.

Id´ee g´en´erale

On consid`ere des graphes orient´es.

Ici on choisitle sommet gris d´ecouvert le plus r´ecemment.

Au lieu d"une

file, on utilise unepile. On d´eroule donc un chemin (gris) le plus loin possible.

Les trois couleurs signifient :

blanc : sommetnon encore d´ecouvert;

gris : sommetd´ecouvert mais dont certainsdescendants n"ont pas encore ´et´e d´ecouverts noir : sommetd´ecouvert ainsi que tous ses descendants.

Algorithme - 1

Comme pour le parcours en largeur, on construitGΠ... mais ici ce sera uneforˆet.

Algorithme - 1

Comme pour le parcours en largeur, on construitGΠ... mais ici ce sera uneforˆet.

On va associer `a tout sommetu?S:

unedatede coloriage en grisd[u]; et

unedatede coloriage en noirf[u]

une date = un entier entre 1 et 2· |S|

Algorithme - 1

Comme pour le parcours en largeur, on construitGΠ... mais ici ce sera uneforˆet.

On va associer `a tout sommetu?S:

unedatede coloriage en grisd[u]; et

unedatede coloriage en noirf[u]

une date = un entier entre 1 et 2· |S| d[u]avant la date d[u],uest en blanc;

entre d[u] et f[u],uest en gris;

apr`es la date f[u],uest en noir.

Parcours en profondeur (init)

Proc´edurePP(

G) //G= (S,A) begin pour chaquex?Sfaire

Couleur[x] := blanc;

Π[x] := nil;

temps:= 0; pour chaquex?Sfaire siCouleur[x] =blancalors

PP-Visiter(G,x);

end

Parcours en profondeur

Proc´edurePP-Visiter(G,s)

Couleur[s] := gris;

temps+ +; d[s] :=temps; pour chaque(s,u)?Afaire siCouleur[u] =blancalors

Π[u] :=s;

PP-Visiter(G,u);

Couleur[s] := noir;

temps+ +; f[s] :=temps;

Exemple

Complexit´e

L"initialisation demande un temps enO(|S|).

La proc´edurePP-Visiterest appel´ee exactement une fois sur chaque sommet.

La complexit´e des boucles

?Pour chaque(s,u)...? de tous les appels

PP-Visiterest donc enO(|A|).

On a donc un algorithme lin´eaire,i.e.enO(|S|+|A|).

Classification des arcs...

Tout arc (v,w) deAest soit un arc deGΠ,

soit...

un arc deGΠ(i.e.Π[w] =v);

unarc?retour?:vest un descendant dewdansGΠ(*); unarcs?avant?:west un descendant devdansGΠ(mais

Π[w]?=v) (*);

unarc?transverse?(tous les autres cas!).

(*) lors de l"examen de (v,w) dansPP-Visiter.

Propri´et´es du Parc. en Profondeur - 1

Propri´et´e 16Pour tout sommetuetv, on a :

soit les intervalles [d[u];f[u]] et [d[v];f[v]] sont disjoints; soit [d[u];f[u]] est contenu dans [d[v];f[v]]; soit [d[v];f[v]] est contenu dans [d[u];f[u]].

Propri´et´es du Parc. en Profondeur - 1

Propri´et´e 16Pour tout sommetuetv, on a :

soit les intervalles [d[u];f[u]] et [d[v];f[v]] sont disjoints; soit [d[u];f[u]] est contenu dans [d[v];f[v]]; soit [d[v];f[v]] est contenu dans [d[u];f[u]].

Supposons d[u]
d[v]
Propri´et´es du Parc. en Profondeur - 1

Propri´et´e 16Pour tout sommetuetv, on a :
soit les intervalles [d[u];f[u]] et [d[v];f[v]] sont disjoints; soit [d[u];f[u]] est contenu dans [d[v];f[v]]; soit [d[v];f[v]] est contenu dans [d[u];f[u]].
Supposons d[u]
d[v] •En d[v],uest gris :PP-Visiter(G,u) n"est pas fini.
Propri´et´es du Parc. en Profondeur - 1

Propri´et´e 16Pour tout sommetuetv, on a :
soit les intervalles [d[u];f[u]] et [d[v];f[v]] sont disjoints; soit [d[u];f[u]] est contenu dans [d[v];f[v]]; soit [d[v];f[v]] est contenu dans [d[u];f[u]].
Supposons d[u]
d[v] •En d[v],uest gris :PP-Visiter(G,u) n"est pas fini. •on va appelerPP-Visiter(G,v?) pour tout (v,v?)?At.q.
Couleur[v?] = blanc.

Propri´et´es du Parc. en Profondeur - 1

Propri´et´e 16Pour tout sommetuetv, on a :
soit les intervalles [d[u];f[u]] et [d[v];f[v]] sont disjoints; soit [d[u];f[u]] est contenu dans [d[v];f[v]]; soit [d[v];f[v]] est contenu dans [d[u];f[u]].
Supposons d[u]
d[v] •En d[v],uest gris :PP-Visiter(G,u) n"est pas fini. •on va appelerPP-Visiter(G,v?) pour tout (v,v?)?At.q.
Couleur[v?] = blanc.
•puis colorierven noir ...etaffecter f[v],
Propri´et´es du Parc. en Profondeur - 1

Propri´et´e 16Pour tout sommetuetv, on a :
soit les intervalles [d[u];f[u]] et [d[v];f[v]] sont disjoints; soit [d[u];f[u]] est contenu dans [d[v];f[v]]; soit [d[v];f[v]] est contenu dans [d[u];f[u]].
Supposons d[u]
d[v] •En d[v],uest gris :PP-Visiter(G,u) n"est pas fini. •on va appelerPP-Visiter(G,v?) pour tout (v,v?)?At.q.
Couleur[v?] = blanc.
•puis colorierven noir ...etaffecter f[v], •finir lesPP-Visiter(G,u?) des autres descendants deu,
Propri´et´es du Parc. en Profondeur - 1

Propri´et´e 16Pour tout sommetuetv, on a :
soit les intervalles [d[u];f[u]] et [d[v];f[v]] sont disjoints; soit [d[u];f[u]] est contenu dans [d[v];f[v]]; soit [d[v];f[v]] est contenu dans [d[u];f[u]].
Supposons d[u]
d[v] •En d[v],uest gris :PP-Visiter(G,u) n"est pas fini. •on va appelerPP-Visiter(G,v?) pour tout (v,v?)?At.q.
Couleur[v?] = blanc.
•puis colorierven noir ...etaffecter f[v], •finir lesPP-Visiter(G,u?) des autres descendants deu, •et enfinaffecter f[u]!
Propri´et´es du Parc. en Profondeur - 1

Propri´et´e 16Pour tout sommetuetv, on a :
soit les intervalles [d[u];f[u]] et [d[v];f[v]] sont disjoints; soit [d[u];f[u]] est contenu dans [d[v];f[v]]; soit [d[v];f[v]] est contenu dans [d[u];f[u]].
Supposons d[u]
d[v] •En d[v],uest gris :PP-Visiter(G,u) n"est pas fini. •on va appelerPP-Visiter(G,v?) pour tout (v,v?)?At.q.
Couleur[v?] = blanc.
•puis colorierven noir ...etaffecter f[v], •finir lesPP-Visiter(G,u?) des autres descendants deu, •et enfinaffecter f[u]!
d[v]>f[u]: alors d[u]
Propri´et´es du Parc. en Profondeur - 2
Propri´et´e 17Pour tout sommetu,v, on a :u→?GΠv? d[u]Propri´et´es du Parc. en Profondeur - 2
Propri´et´e 17Pour tout sommetu,v, on a :u→?GΠv? d[u]Propri´et´es du Parc. en Profondeur - 2
Propri´et´e 17Pour tout sommetu,v, on a :u→?GΠv? d[u]Propri´et´es du Parc. en Profondeur - 2
Propri´et´e 17Pour tout sommetu,v, on a :u→?GΠv? d[u]Propri´et´es du Parc. en Profondeur - 2
Propri´et´e 17Pour tout sommetu,v, on a :u→?GΠv? d[u](2)?(1)soientuetvtq d[u] u?→?GΠv. On choisitvde mani`ere `a minimiser d[v].
Propri´et´es du Parc. en Profondeur - 2
Propri´et´e 17Pour tout sommetu,v, on a :u→?GΠv? d[u](2)?(1)soientuetvtq d[u] u?→?GΠv. On choisitvde mani`ere `a minimiser d[v].
Propri´et´es du Parc. en Profondeur - 2
Propri´et´e 17Pour tout sommetu,v, on a :u→?GΠv? d[u](2)?(1)soientuetvtq d[u] u?→?GΠv. On choisitvde mani`ere `a minimiser d[v]. Consid´eronsw= Π(v) (il existe car d[u]

[PDF] Parcours de graphes - IRIF