1 Exploration d'un graphe / Parcours 2 Parcours en largeur (BFS) Partition des sommets en couches Principe de l'algorithme Implémentation Complexité
Previous PDF | Next PDF |
[PDF] Algorithmique des graphes - Cours 3 – Parcours en largeur - LaBRI
Algorithme 1 : Parcours en largeur BFS(G,s) Données : graphe G, sommet de départ s File D (initialisée à vide), marque des sommets (initialisé à Faux) début
[PDF] Parcours dun graphe
1 avr 2013 · Parcours en largeur : principe de l'algorithme Vous devez parcourir toutes les pages d'un site web Les pages sont les sommets d'un graphe
[PDF] Chapitre 3 : Exploration dun graphe - Algorithmique de - LIPN
1 Exploration d'un graphe / Parcours 2 Parcours en largeur (BFS) Partition des sommets en couches Principe de l'algorithme Implémentation Complexité
[PDF] Parcours de graphes - Université de Montréal
Un parcours en profondeur (DFS) d'un graphe G Visite tous les sommets et toutes les arêtes de G Détermine si G est connexe ou non Calcule les
[PDF] Première partie : Algorithmique avancée pour les graphes - CNRS
Algorithme 2 : Parcours en largeur d'un graphe 1 Fonction BFS(g, s0) Entrée : Un graphe g et un sommet s0 de g Postcondition : Retourne une arborescence
[PDF] Algorithmes pour les graphes - CNRS
3 Structures de données pour représenter un graphe 4 Parcours de graphes Généralités sur les parcours Parcours en largeur (BFS) Parcours en profondeur
[PDF] Parcours de graphes - IRIF
2 nov 2010 · Correction du parcours en largeur Théor`eme Soient G = (S,A) un graphe non- orienté et s ∈ S un sommet L'algorithme PL(G,s) : 1 découvre
[PDF] Algorithmique — L3 TD 7 : Parcours de Graphes - IRIF
L'arbre de parcours en largeur résultant sera présenté par un schéma dans lequel les sommets de profondeur égale seront mis `a la même hauteur, le sommet
[PDF] Parcours de graphes - IGM
Parcours de graphes Exemple 9 Voici (a) un arbre binaire, et les numérotations des sommets que l'on peut obtenir en le parcourant (b) en profondeur ou (c) en
[PDF] Parcours de graphes
sommets du graphe Il y a deux stratégies de parcours différentes : partant d'un sommet, le graphe est parcouru ◦ en largeur ◦ en profondeur 4
[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
Chapitre 3: Exploration d'un graphe
Algorithmique de graphes
Sup Galilee-INFO2
Sylvie Borne
2012-2013
Chapitre 3
: Exploration d'un graphe-1/35 Plan1Exploration 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/35Exploration 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/35Exploration 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/35Partition 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/35Partition 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 C1=fx2Vjd(r;x) = 1g
C2=fx2Vjd(r;x) = 2g
C i=fx2Vjd(r;x) =igChapitre 3
: Exploration d'un graphe- Parcours en largeur (BFS) 8/35Partition des sommets en couches
Exemple:
rRemarque:
Il n'existe pas d'ar^etes entre deux couchesCietCjsijijj 2.Chapitre 3
: Exploration d'un graphe- Parcours en largeur (BFS) 9/35Partition des sommets en couches
Remarque:
Cas oriente
On denit les couches de la m^eme maniere, en considerant les descendants. C1=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/35Principe 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/35Implementation
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/35Implementation
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/35Implementation
!Procedure LARGEUR (G: graphe,r: sommet) pouri= 1 anfaireMarque[i] 0
n pour t^ete 1 queue 1File[t^ete] r
Marque[r] 1
Chapitre 3
: Exploration d'un graphe- Parcours en largeur (BFS) 14/35Implementation
tantquet^etequeuefaire x File[t^ete] poury parcourant la liste des successeurs de xfaire siMarque[y] = 0alorsMarque[y]=Marque[x]+1
queue queue+1File[queue] y
nsi n pour t^ete t^ete +1 n tantqueChapitre 3
: Exploration d'un graphe- Parcours en largeur (BFS) 15/35Implementation
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/35Implementation
Exemple:
Soit un grapheGet une representation par listes d'adjacence.v7v2v1v5
v8v3v4v6
Parcours en largeur a partir
de la racine 7.1 2 3 4 5 6 7 84456 3 2
7 4 1 3 2 7 1 4 6 1 3 2 1 6 1 5 8 3 2 7File1 2 3 4 5 6 7 8
Marque
Repartition en couches
Chapitre 3: Exploration d'un graphe- Parcours en largeur (BFS) 17/35Complexite
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/35Tester 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/35Tester 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
v2v3,v1v4,v5v6.*
***v4v8v3v6v1****v7v2v5
Chapitre 3
: Exploration d'un graphe- Parcours en largeur (BFS) 20/35Tester si un graphe est biparti
Exemple:
v 1 v 5v 8v 10 v 9v 2v3 v 6v7v4Parcours en largeur a partir de la racinev1et en suivant l'ordre
lexicographique.File1 2 3 4 5 6 7 8 9 10
Marque
Chapitre 3: Exploration d'un graphe- Parcours en largeur (BFS) 21/35Tester si un graphe est biparti
Exemple:
v 1 v 4v5 v 7v9v 10v 3v2 v 6v8* *B A v1v5v4v10v9v7
v2v6v8v3Parcours 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/35Parcours 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 elementaire0de 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/35Principe 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/35Principe 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/35Implementation
Implementation:
!Procedure PROFONDEUR (G: graphe,r: sommet)pouri= 1 anfaireMarque[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+1Pile[h] y
nsiMettre a jour PS[x]
sinon h h-1 nsi n tantque Chapitre 3: Exploration d'un graphe- Parcours en profondeur (DFS) 26/35Exemple
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 1v71 2 3 4 5 6 7 8
PS :136810131619
Parcours en profondeur a partir de la racine 2.
PileChapitre 3
: Exploration d'un graphe- Parcours en profondeur (DFS) 27/35Exemple
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 814 57
6
321 2 3 4 5 6 7 8
PS :136810131619
Parcours en profondeur a partir de la racine 2.
5 2 67267Pile
348 2 61