[PDF] Chapitre 3 : Exploration d’un graphe

Parcours de graphes - Université de Montréal

Parcours 11 Parcours en largeur (Breadth-First Search) Un parcours en largeur (BFS) 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 composantes connexes de G Calcule une forêt couvrante pour G L’algorithme de parcours en largeur (BFS) d’un graphe G prend un temps O(n+m)

Parcours dun graphe

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 et un lien entre deux pages est une ar^ete entre ces deux sommets 1 Dans le parcours en largeur, on utilise une le On en le le sommet de

Parcours de graphes - miashs-wwwu-gafr

Arbre de parcours en largeur Le parcours en largeur génère un arbre : La racine est le sommet de départ Les noeuds de l’arbre sont les sommets du graphe qui peuvent être atteints depuis le sommet de départ Les arêtes de l’arbre sont celles du graphe, qui relient un sommet à son prédécesseur (pred) au cours du parcours Remarque:

Parcours de graphes - IRIF

Correction du parcours en largeur Th´eor`eme Soient G = (S,A) un graphe non-orient´e et s∈ S un sommet L’algorithme PL(G,s) : 1 d´ecouvre tous les sommets atteignables depuis s et

Parcours de graphes - WordPresscom

Parcours en largeur"# $ &'(&)* +, # -"#( * $# of this page, which show the progress of DFS and BFS for our sample graph mediumG txt, make plain the differ - ences between the paths that are dis-covered by the two approaches DFS wends its way through the graph, stor - ing on the stack the points where other

Algorithmique des graphes quelques notes de cours

1 Modi er l'algorithme de parcours en largeur a n de récupérer les composantes connexes du graphe en entrée 2 Appliquer le parcours en largeur à la recherche d'un plus court chemin entre deux som-mets xet ydu graphe G 3 Proposer une version du parcours en largeur où la le a_traiter est simulée à l'aide d'un tableau de néléments

Chapitre 3 : Exploration d’un graphe

Lors d’un parcours en largeur, on applique la r egle "premier marqu e-premier explor e" i e Pour construire les couches, on explore les sommets en respectant l’ordre dans lequel ils ont et e marqu es Chapitre 3 : Exploration d’un graphe - Parcours en largeur (BFS) 12/35

Parcours de graphes - FIL Lille 1

Voici les quatre premières étapes du parcours en largeur sur le graphe de l’exemple 10au départ du sommet 0 : Algorithmique des graphes 27

GRAPHES ET ALGORITHMES - LAAS

Parcours de Graphe (2 cours) Principe du parcours Parcours en profondeur Parcours en largeur Premières applications d’un algorithme de parcours Connexité – Forte connexité Divers , 3 Optimisation et Graphes Plus courts chemins (2 cours) Problèmes de flots (3 cours) 6

[PDF] fiche revision decolonisation

[PDF] parcours en profondeur d'un graphe en c

[PDF] théorie des graphes python

[PDF] parcours en largeur graphe

[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

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 3quotesdbs_dbs44.pdfusesText_44