[PDF] Chapitre 3 : Exploration dun graphe - Algorithmique de graphes

View - Download Chapitre 3 : Exploration dun graphe - Algorithmique de graphes

Previous PDF

Next PDF

Chapitre 3: Exploration d'un graphe

Algorithmique de graphes

Sup Galilee-INFO2

Sylvie Borne

2012-2013

Chapitre 3

: Exploration d'un graphe-1/35 Plan

1Exploration d'un graphe / Parcours

2Parcours en largeur (BFS)

Partition des sommets en couches

Principe de l'algorithme

Implementation

Complexite

Application : tester si un graphe est biparti

3Parcours en profondeur (DFS)

Prolongement d'une cha^ne elementaire

Principe de l'algorithme

Implementation

Complexite

4Parcours et connexite

5Parcours et graphes orientes

Chapitre 3: Exploration d'un graphe-2/35

Exploration de graphes

En utilisant un graphe comme modele, on a souvent besoin d'un examen exhaustif des sommets. On peut concevoir cet examen comme une promenade le long des arcs/ar^etes au cours de laquelle on visite les sommets. Les algorithmes de parcours de graphesservent de base a bon nombre d'algorithmes. Ils n'ont pas une nalite intrinseque. Le plus souvent, un parcours de graphe est un outil pour etudier une propriete globale du graphe :le graphe est-il connexe? le graphe est-il biparti? le graphe oriente est-il fortement connexe? quels sont les sommets d'articulation?

Chapitre 3: Exploration d'un graphe-3/35

Exploration de graphes

Probleme: On appelle exploration / parcoursd'un graphe, tout procede deterministe qui permet de choisir, a partir des sommets visites, le sommet suivant a visiter. Le probleme consiste a determiner un ordresur les visites des sommets.Remarque: L'ordre dans l'examen des sommets induit :une numerotation des sommets visites le choix d'une ar^ete pour atteindre un nouveau sommet a partir des sommets deja visites.

Chapitre 3

: Exploration d'un graphe- Exploration d'un graphe / Parcours 4/35

Exploration de graphes

Attention : La notion d'exploration / parcours peut ^etre utilisee dans les graphes orientes comme non-orientes. Dans la suite, nous supposerons que le graphe est non-oriente. L'adaptation au cas des graphes orientes s'eectue sans aucune diculte.

Chapitre 3

: Exploration d'un graphe- Exploration d'un graphe / Parcours 5/35

Exploration de graphes

Denition:racine

Le sommet de depart, xe a l'avance, dont on souhaite visiter tous les descendants est appele racinede l'exploration.

Denition:parcours

Un parcoursde racinerest une suiteLde sommets telle que1rest le premier sommet deL,2chaque sommet appara^t une fois et une seule dansL,3tout sommet sauf la racine est adjacent a un sommet place

avant lui dans la liste.

Deux types d'exploration :parcours en largeur

parcours en profondeur Chapitre 3: Exploration d'un graphe- Exploration d'un graphe / Parcours 6/35

Partition des sommets en couches

Denition:distance

Soientx;y2V, on pose

d(x;y)= longueur d'un plus court chemin (siG= (V;A) un graphe oriente) (ou plus courte cha^ne, siG= (V;E) un graphe non-oriente) entrexety(en nombre d'ar^etes). d(x;y) est appele distanceentrexety.

Remarque:

S'il n'existe pas de cha^ne (chemin) entrexety,d(x;y) = +inf.

Chapitre 3

: Exploration d'un graphe- Parcours en largeur (BFS) 7/35

Partition des sommets en couches

Denition:partition en couches

On appelle partition en couchesassociee a un sommet sourcer (appele racine), la suite d'ensembles denie iterativement comme suit : C 0=frg C

1=fx2Vjd(r;x) = 1g

C

2=fx2Vjd(r;x) = 2g

C i=fx2Vjd(r;x) =ig

Chapitre 3

: Exploration d'un graphe- Parcours en largeur (BFS) 8/35

Partition des sommets en couches

Exemple:

r

Remarque:

Il n'existe pas d'ar^etes entre deux couchesCietCjsijijj 2.

Chapitre 3

: Exploration d'un graphe- Parcours en largeur (BFS) 9/35

Partition des sommets en couches

Remarque:

Cas oriente

On denit les couches de la m^eme maniere, en considerant les descendants. C

1=ensemble des sommets descendants (successeurs) der.

!Ici, il peut y avoir des arcs entreCietCjavecij+ 2.

Ceux-ci vont necessairement deCiversCj.

Chapitre 3

: Exploration d'un graphe- Parcours en largeur (BFS) 10/35

Principe de l'algorithme

On visite les sommets en construisant les couches dans l'ordre. Idee:Ci+1V(Ci) ouV(Ci) designe l'ensemble des voisins des sommets appartenant aCi. C i+1s'obtient a partir deCien deployant, pour chaque sommet de C i, et ce dans l'ordre, la liste des voisins non encore marques.

Algorithme:

On part deret on visite successivement les sommets.on visite d'abord les voisins (successeurs) der.

Ces sommets constituentC1.C

i+1est obtenu en visitant tous les sommets successeurs des sommets deCi, non encore visites.

Chapitre 3

: Exploration d'un graphe- Parcours en largeur (BFS) 11/35

Implementation

Denition:sommet marque

Un sommet est dit marques'il a ete place dans une coucheCi.

Denition:sommet explore

Un sommet marque est dit explorelorsque l'on aura marque tous ses voisins.

Propriete:

Lors d'un parcours en largeur, on applique la regle "premier marque-premier explore". i.e.Pour construire les couches, on explore les sommets en respectant l'ordre dans lequel ils ont ete marques.

Chapitre 3

: Exploration d'un graphe- Parcours en largeur (BFS) 12/35

Implementation

La gestion des sommets est realisable au moyen d'une structure de donnees appelee le.

Denition:le

Une le(queue en anglais) est une structure de donnees basee sur le principe du "Premier entre, premier sorti" (FIFO en anglais), ce qui veut dire que les premiers elements ajoutes a la le seront les premiers a ^etre recuperes.

Implementation:

On utilise une le de taillen+ 1 oun=jVj.

On associe a chaque sommet un numero.

La racine aura le numero 1.

Les sommets marques a partir d'une coucheCiauront le numero i+ 1.

On utilise deux curseurs : t^ete et queue.

Chapitre 3: Exploration d'un graphe- Parcours en largeur (BFS) 13/35

Implementation

!Procedure LARGEUR (G: graphe,r: sommet) pouri= 1 anfaire

Marque[i] 0

n pour t^ete 1 queue 1

File[t^ete] r

Marque[r] 1

Chapitre 3

: Exploration d'un graphe- Parcours en largeur (BFS) 14/35

Implementation

tantquet^etequeuefaire x File[t^ete] poury parcourant la liste des successeurs de xfaire siMarque[y] = 0alors

Marque[y]=Marque[x]+1

queue queue+1

File[queue] y

nsi n pour t^ete t^ete +1 n tantque

Chapitre 3

: Exploration d'un graphe- Parcours en largeur (BFS) 15/35

Implementation

Remarque:

L'ordre de visite des sommets depend de l'ordre des listes d'adjacence car on doit parcourir ces listes.

Remarque:

L'algorithme determine, pour chaque sommetxvisite, une cha^ne elementaire unique derax.

Chapitre 3

: Exploration d'un graphe- Parcours en largeur (BFS) 16/35

Implementation

Exemple:

Soit un grapheGet une representation par listes d'adjacence.v

7v2v1v5

v

8v3v4v6

Parcours en largeur a partir

de la racine 7.1 2 3 4 5 6 7 84

456 3 2

7 4 1 3 2 7 1 4 6 1 3 2 1 6 1 5 8 3 2 7File

1 2 3 4 5 6 7 8

Marque

Repartition en couches

Chapitre 3: Exploration d'un graphe- Parcours en largeur (BFS) 17/35

Complexite

Espace:

representation du graphe :O(n+m) structure le :O(n) tableau marque :O(n) )complexite dans l'espace :O(n+m)

Temps:

marquage :noperations exploration : chaque sommetxnecessitedxoperations donc en toutX x2Vd x= 2jEj= 2m )complexite en temps :O(n+m) Chapitre 3: Exploration d'un graphe- Parcours en largeur (BFS) 18/35

Tester si un graphe est biparti

Denition:stable

On appelle stable, un ensemble de sommets induisant un sous-graphe sans ar^ete.

Denition:biparti

On appelle graphe biparti, un grapheG= (V;E) pour lequelV peut ^etre partitionne en deux stablesAetB.

Propriete:

Un grapheGest biparti si et seulement siGest

2chromatique.

Chapitre 3

: Exploration d'un graphe- Parcours en largeur (BFS) 19/35

Tester si un graphe est biparti

Algorithme:

Faire un parcours en largeur deG.Colorer les niveaux pairs en rouge, les niveaux impairs en vert. Si aucun arc/ar^ete entre les sommets d'un m^eme niveau Alors le graphe est biparti Sinon le graphe n'est pas biparti.

Exemple:

Le graphe de l'exemple

precedent n'est pas biparti.

Probleme avec les ar^etes

v

2v3,v1v4,v5v6.*

***v4v8v3v6v

1****v7v2v5

Chapitre 3

: Exploration d'un graphe- Parcours en largeur (BFS) 20/35

Tester si un graphe est biparti

Exemple:

v 1 v 5v 8v 10 v 9v 2v3 v 6v7v

4Parcours en largeur a partir de la racinev1et en suivant l'ordre

lexicographique.File

1 2 3 4 5 6 7 8 9 10

Marque

Chapitre 3: Exploration d'un graphe- Parcours en largeur (BFS) 21/35

Tester si un graphe est biparti

Exemple:

v 1 v 4v5 v 7v9v 10v 3v2 v 6v8* *B A v

1v5v4v10v9v7

v

2v6v8v3Parcours en largeur a partir de la racinev1

et en suivant l'ordre lexicographique.

File :12345106879

Marque :

1 2 3 4 5 6 7 8 9 101223345453

Chapitre 3

: Exploration d'un graphe- Parcours en largeur (BFS) 22/35

Parcours en profondeur (DFS)

Denition:prolongement d'une cha^ne elementaire

Soit une cha^ne elementaire entre deux sommetsx0etxp. On appelle prolongement de = (e1;e2;:::;ep), une cha^ne elementaire

0de la forme

0= (e1;e2;:::;ep;ep+1)

ouep+1est une nouvelle ar^ete ajoutee a la cha^ne. Siep+1est entrexpetxp+1, on dit que la cha^ne est prolongee a x p+1.

Remarque:

Il est clair que n'admet pas de prolongement si et seulement si tous les voisins dexpse trouvent dans .

Chapitre 3

: Exploration d'un graphe- Parcours en profondeur (DFS) 23/35

Principe de l'algorithme DFS

On part du sommetr.

Lorsque l'on arrive a un sommetx, on ne l'explore pas, on visite un de ses voisins non encore visite, on cherche donc a prolonger le chemin derax.

Propriete:

Lors d'un parcours en profondeur, on applique la rege "Dernier marque, premier explore". i.e.On explore les sommets dans l'ordre inverse de celui utilise pour les marquer.

Remarque:

On pourra utiliser "ferme" pour "explore".

Chapitre 3

: Exploration d'un graphe- Parcours en profondeur (DFS) 24/35

Principe de l'algorithme DFS

La gestion des sommets est realisable au moyen d'une structure de donnees appelee pile.

Denition:pile

Une pile(stack en anglais) est une structure de donnees basee sur le principe du dernier arrive, permier sorti (LIFO en anglais), ce qui veut dire que les derniers elements ajoutes a la pile seront les premiers a ^etre recuperes.

Chapitre 3

: Exploration d'un graphe- Parcours en profondeur (DFS) 25/35

Implementation

Implementation:

!Procedure PROFONDEUR (G: graphe,r: sommet)pouri= 1 anfaire

Marque[i] faux

n pour h 1 (hauteur de pile)

Pile[h] r

tantqueh>0faire x Pile[h] siPS[x]6= 0alors y LS[PS[x]] siMarque[y]=fauxalorsMarque[y]=vrai h h+1

Pile[h] y

nsi

Mettre a jour PS[x]

sinon h h-1 nsi n tantque Chapitre 3: Exploration d'un graphe- Parcours en profondeur (DFS) 26/35

Exemple

Exemple:

Soit un grapheGet une representation par table des successeurs.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

LS26618453534727165827

v 3 v 4v 5v 8 v 6v 2 v 1v

71 2 3 4 5 6 7 8

PS :136810131619

Parcours en profondeur a partir de la racine 2.

Pile

Chapitre 3

: Exploration d'un graphe- Parcours en profondeur (DFS) 27/35

Exemple

Exemple:

Soit un grapheGet une representation par table des successeurs.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

LS26618453534727165827

v 3 v 4v 5v 8 v 6v 2 v 1v 7 81
4 57
6

321 2 3 4 5 6 7 8

PS :136810131619

Parcours en profondeur a partir de la racine 2.

5 2 67

267Pile

34
8 2 61

Chapitre 3

: Exploration d'un graphe- Parcours en profondeur (DFS) 28/35

Implementation

Remarque:

quotesdbs_dbs16.pdfusesText_22

[PDF] parcours en profondeur itératif

[PDF] algorithme parcours en profondeur python

[PDF] parcours en largeur graphe java

[PDF] conflit de puissance définition

[PDF] parcours lecture acces pas cher

[PDF] parcours lecture pdf

[PDF] parcours lecture le petit chaperon rouge

[PDF] parcours lecture acces avis

[PDF] parcours lecture occasion

[PDF] coexistence pacifique cours

[PDF] archives militaire en ligne

[PDF] livret militaire en ligne

[PDF] la coexistence pacifique de 1953 ? 1962 pdf

[PDF] cornière catnic

[PDF] corniere galva pour brique