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 d epart (on visite la page index du site)
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 - 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 - 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 - WordPresscom
FIGURE 6: Arbre en largeur sur un graphe de 250 sommets [Sedgewick & Wayne] Lors d’un parcours en largeur5 (breadth-first search), on enfile les voisins dans 5 (fr):parcours en largeur une file FIFO (queue) Dans la version ci-dessous, on maintient la distance d à partir du sommet de source Le parcours prend O(jVj+jEj) temps avec
Parcours de graphes - Formations en Informatique de Lille fil
2 2 2Parcours de graphes en largeur Une fois le parcours en profondeur d’arbre généralisé au cas des graphes non orientés, la généralisation aux graphes du parcours d’arbre en largeur ne présente pas de difficulté ma-jeure On manipule toujours une liste résultat dans laquelle on insère les sommets au fur et
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] 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
Parcours de graphes
Heike Ripphausen-Lipa-BeuthUniversity of Applied Science -Berlin J.M. Adam -Université de Grenoble Alpes -GrenobleLabyrinthe
2 A BTrouver un chemin de
A à B à travers le
labyrintheHeike Ripphausen-Lipa& Jean-Michel Adam
Labyrinthe
A nouveau le problème peut être
modélisé par un graphe :Le labyrinthe peut être représenté par
un graphe similaire au graphe pour la représentation d'un planLe problème consiste à trouver un
chemin de A à B, par un parcours systématique du graphe.Heike Ripphausen-Lipa& Jean-Michel Adam3
Parcoursde graphe
Il existe de nombreux algorithmes de
parcours systématiques de tous les 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
4Heike Ripphausen-Lipa& Jean-Michel Adam
Parcours en largeur
Breadth
-First-Search (BFS)Parcoursenlargeur
Le parcours en largeur consiste à
parcourir d'abord tous les voisins d'un sommet donné, puis on parcourt les voisins des voisins, etc.Le parcours se fait en "largeur" avant de
se faire en "profondeur"De nombreux algorithmes sont basés
sur cette stratégie, par exemple l'algorithme deDijkstrapour trouver les
chemins les plus courts6Heike Ripphausen-Lipa& Jean-Michel Adam
Structure de donnéespour le
parcoursenlargeur Structure de donnéespour se rappelerles sommets qui n'ontpas étécomplètementprisencompte:File :puisque chaque nouveau sommet visité est
positionné à la fin de la file d'attente; les sommets les premiers visités sont les premiers supprimés de la file. Structure de données pour représenter le graphe afin d'obtenir une mise en oeuvre efficaceListed'adjacence,puisque les voisins de chaque
sommet sont systématiquement visités7Heike Ripphausen-Lipa& Jean-Michel Adam
Parcoursenlargeur
Pour chaquesommeton calculles informations
suivantes: dist: la distance d'un sommet au sommet de départ (le sommet où commence la recherche) pred: le prédécesseur, c'est-à-dire le sommet depuis lequel le sommet actuel a été atteint la première fois coul: une des couleurs blanc, gris, noir8Heike Ripphausen-Lipa& Jean-Michel Adam
Parcoursenlargeur
Signification des
couleurs:Blanc : le sommetn'apas encore été
visitéGris : le sommeta étévisité, mais
toussesvoisinsne l'ontpas encoreété
Noir: le sommetet toussesvoisins
ontétévisités9Heike Ripphausen-Lipa& Jean-Michel Adam
Algorithmedu parcoursenlargeur
12.09.2019Heike Ripphausen-Lipa10
Algorithmparcours-largeur(s)
s : le sommetde départ, Q : unefile init-parcours-largeur(s) tantquenon Q.fileVideQ.defiler(u)
pourtoutsommetv adjacentà u faire si(coul[v] = blanc) // v pasencorevisité alorscoul[v] gris dist[v] dist[u] + 1 pred[v] uQ.enfiler(v)
fsi fpour coul[u] noir; ftqHeike Ripphausen-Lipa & Jean-Michel Adam
11 init-parcours-largeur(s) s : le sommetde départ, Q : unefile coul[s] gris dist[s] 0 pred[s] NILQ.enfiler(s)
coul[v] blanc dist[v] MAXINT pred[v] NIL fpourAlgorithmedu parcoursenlargeur
Heike Ripphausen-Lipa& Jean-Michel Adam
12 rstu vwxy iLa valeurplacéedanschaquesommetestdist, pas de valeursignifieMAXINT Q s0Parcoursenlargeur
Heike Ripphausen-Lipa& Jean-Michel Adam
13 rstu vwxy Q 0Visiterle sommets:
Parcourirtousles voisinsde s
r 1 w 1 0Parcoursenlargeur
Heike Ripphausen-Lipa& Jean-Michel Adam
14 rstu vwxy Q 0Visiterle sommetr:
Parcourirtousles voisinsde r
w 1 v 1 0 2Parcoursenlargeur
Heike Ripphausen-Lipa& Jean-Michel Adam
15 rstu vwxy Q 0Visiterle sommetw:
Parcourirtousles voisinsde w
v 1 12 t 2 x 1 0 2Parcoursenlargeur
Heike Ripphausen-Lipa& Jean-Michel Adam
16Visiterle sommetv:
Parcourirtousles voisinsde v
rstu vwxy Q 01 12 210 2 tx
Parcoursenlargeur
Heike Ripphausen-Lipa& Jean-Michel Adam
17Visiterle sommett:
Parcourirtousles voisinsde t
rstu vwxy Q 01 12 210 2 1 132
xu
Parcoursenlargeur
Heike Ripphausen-Lipa& Jean-Michel Adam
18 rstu vwxy Q 0Visiterle sommetx:
Parcourirtousles voisinsde x
1 12 210 2 1 132
uy 3
Parcoursenlargeur
Heike Ripphausen-Lipa& Jean-Michel Adam
19 rstu vwxy Q 0Visiterle sommetu:
Parcourirtousles voisinsde u
y 1 12 210 2 1 132
322
3
Parcoursenlargeur
Heike Ripphausen-Lipa& Jean-Michel Adam
20 rstu vwxy Q 0Visiterle sommety:
Parcourirtousles voisinsde y
1 12 210 2 1 132
322
3
Parcoursenlargeur
Heike Ripphausen-Lipa& Jean-Michel Adam
Exécutionde l'algorithmedans
unetable 21som.rstwuvxy pred dist
Heike Ripphausen-Lipa& Jean-Michel Adam
22som.rstwuvxy predsNILwstrwx dist10213223