[PDF] Parcours de graphes - miashs-wwwu-gafr

Introduction to Algorithms, Third Edition

We have included 957 exercises and 158 problems Each section ends with exer-cises, and each chapter ends with problems The exercises are generally short ques-tions that test basic mastery of the material Some are simple self-check thought exercises, whereas others are more substantial and are suitable as assigned home-work

Parcours de graphes - miashs-wwwu-gafr

Algorithmique - 3ème édition Thomas H Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein Cours avec 957 exercices et 158 problèmes – Dunod juin 2010 Heike Ripphausen -Lipa & Jean-Michel Adam 27

Algorithmique et structure de données 2

Thomas H Cormen, Charles E Leiserson, Ronald L Rivest Algorithmique - 3ème édition - Cours avec 957 exercices et 158 problèmes Broché, Dunod, 2010 Rémy Malgouyres, Rita Zrour et Fabien Feschet Inititiation à l’algorithmique et à la programmation en C : cours avec 129 exercices corrigés 2ième Edition Dunod, Paris, 2011

Calcul de coût d’algorithme - POLARIS

[1]Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein Algorithmique - 3ème édition - Cours avec 957 exercices et 158 problèmes Dunod, 3e édition edition, 6 2010 [2]Ronald Graham, Donald E Knuth, and Oren Patashnik Mathématiques concrètes International Thomson publishing France, 2e éd edition, 1998

III - Programme détaillé par matière des semestres (1 fiche

Thomas H Cormen, Charles E Leiserson, Ronald L Rivest Algorithmique - 3ème édition - Cours avec 957 exercices et 158 problèmes Broché, Dunod, 2010 Rémy Malgouyres, Rita Zrour et Fabien Feschet Iitiatio v à l’algoithiue et à la p og a u uatio e v C : cours avec 129 exercices corrigés 2ième Edition Dunod, Paris, 2011

Canevas d’aedeet - univ-batna2dz

Thomas H Cormen, Charles E Leiserson, Ronald L Rivest Algorithmique - 3ème édition - Cours avec 957 exercices et 158 problèmes Broché, Dunod, 2010 Rémy Malgouyres, Rita Zrour et Fabien Feschet Iitiatioàl’algoithiueetàlapogaatioe C : cours avec 129 exercices corrigés 2ième Edition Dunod, Paris, 2011 ISBN : 978-2-10-055703-5

[eBooks] Biochimie Générale 11e édition: Cours Et Questions

Biochimie générale 11e édition: Cours et questions de révision By Jacques-Henry Weil Read Online Share This Previous Post Next Post ‹‹ Newer Post Older Post ›› Meilleur Livre Algorithmique - 3ème édition - Cours avec 957 exercices et 158 problèmes Livre Gratuit Ebook Algorithmique - 3ème édition - Cours avec 957 exercices

[PDF] séquence presse cycle 3

[PDF] algorithmique et programmation exercices corrigés pdf

[PDF] séquence sur la presse

[PDF] séquence 4ème français

[PDF] telecharger livre algorithme gratuit

[PDF] poésie sur l'école

[PDF] poesie ecole maurice careme

[PDF] poème sur l'école d'autrefois

[PDF] poème sur l'école collège

[PDF] poésie école primaire cycle 2

[PDF] poésie école ce2

[PDF] dit de la force de l'amour analyse

[PDF] poèmes engagés

[PDF] vivaldi ete 3eme mouvement

[PDF] vivaldi les 4 saisons l'automne

Parcours de graphes

Heike Ripphausen-Lipa-BeuthUniversity of Applied Science -Berlin J.M. Adam -Université de Grenoble Alpes -Grenoble

Labyrinthe

2 A B

Trouver un chemin de

A à B à travers le

labyrinthe

Heike 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 plan

Le 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 de

Dijkstrapour trouver les

chemins les plus courts

6Heike 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 efficace

Listed'adjacence,puisque les voisins de chaque

sommet sont systématiquement visités

7Heike 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, noir

8Heike 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és

9Heike 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.fileVide

Q.defiler(u)

pourtoutsommetv adjacentà u faire si(coul[v] = blanc) // v pasencorevisité alorscoul[v] gris dist[v] dist[u] + 1 pred[v] u

Q.enfiler(v)

fsi fpour coul[u] noir; ftq

Heike 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] NIL

Q.enfiler(s)

coul[v] blanc dist[v] MAXINT pred[v] NIL fpour

Algorithmedu parcoursenlargeur

Heike Ripphausen-Lipa& Jean-Michel Adam

12 rstu vwxy iLa valeurplacéedanschaquesommetestdist, pas de valeursignifieMAXINT Q s0

Parcoursenlargeur

Heike Ripphausen-Lipa& Jean-Michel Adam

13 rstu vwxy Q 0

Visiterle sommets:

Parcourirtousles voisinsde s

r 1 w 1 0

Parcoursenlargeur

Heike Ripphausen-Lipa& Jean-Michel Adam

14 rstu vwxy Q 0

Visiterle sommetr:

Parcourirtousles voisinsde r

w 1 v 1 0 2

Parcoursenlargeur

Heike Ripphausen-Lipa& Jean-Michel Adam

15 rstu vwxy Q 0

Visiterle sommetw:

Parcourirtousles voisinsde w

v 1 12 t 2 x 1 0 2

Parcoursenlargeur

Heike Ripphausen-Lipa& Jean-Michel Adam

16

Visiterle sommetv:

Parcourirtousles voisinsde v

rstu vwxy Q 01 12 21
0 2 tx

Parcoursenlargeur

Heike Ripphausen-Lipa& Jean-Michel Adam

17

Visiterle sommett:

Parcourirtousles voisinsde t

rstu vwxy Q 01 12 21
0 2 1 132
xu

Parcoursenlargeur

Heike Ripphausen-Lipa& Jean-Michel Adam

18 rstu vwxy Q 0

Visiterle sommetx:

Parcourirtousles voisinsde x

1 12 21
0 2 1 132
uy 3

Parcoursenlargeur

Heike Ripphausen-Lipa& Jean-Michel Adam

19 rstu vwxy Q 0

Visiterle sommetu:

Parcourirtousles voisinsde u

y 1 12 21
0 2 1 132
322
3

Parcoursenlargeur

Heike Ripphausen-Lipa& Jean-Michel Adam

20 rstu vwxy Q 0

Visiterle sommety:

Parcourirtousles voisinsde y

1 12 21
0 2 1 132
322
3

Parcoursenlargeur

Heike Ripphausen-Lipa& Jean-Michel Adam

Exécutionde l'algorithmedans

unetable 21
som.rstwuvxy pred dist

Heike Ripphausen-Lipa& Jean-Michel Adam

22
som.rstwuvxy predsNILwstrwx dist10213223

Trouverun cheminde sà u:

u t w s

Exécutionde l'algorithmedans

unetable

Heike Ripphausen-Lipa& Jean-Michel Adam

Temps d'exécution du parcours

en largeur

Pour un graphe de nsommets et marêtes :

Initialiser les information col, distand predpour

tous les sommets : O(n)

Chaque sommet est place une seule fois dans la

queue; temps pour tous les sommets : O(n) Chaque sommet est supprimé une seule fois de la file; temps pour tous les sommets : O(n) Pour chaque sommet supprimé de la file, on examine tous les voisins; temps d'exécution: O(m) Temps d'exécution pour toutes ces étapes est O( n+m

23Heike Ripphausen-Lipa& Jean-Michel Adam

Arbrede parcoursenlargeur

Le parcoursenlargeurgénèreun arbre:

La racineestle sommetde départ

Les noeudsde l'arbresontles sommetsdu graphe

qui peuventêtreatteintsdepuisle sommetde départ. Les arêtes de l'arbresontcellesdu graphe, qui relient un sommetà son prédécesseur(pred) au coursdu parcours Remarque: tous les sommets du graphe ne doivent pas appartenir à l'arbre car il peut exister des sommets inaccessibles !

24Heike Ripphausen-Lipa& Jean-Michel Adam

25
rstu vwxy 01 12 21
0 2 132
322
3 3

Arêtes de l'arbrede parcours

enlargeur

Arcs du graphequi

n'appartiennentpas à l'arbre de parcoursenlargeur

Arbrede parcoursenlargeur

Heike Ripphausen-Lipa& Jean-Michel Adam

Distance du plus court chemin

Definition:

La distance du plus court cheminįs,v)d'un

sommetsà un sommetvestdéfinieainsi: min{ Dist (w)| westun cheminde sà v dansGet Dist(w)estle nombred'arcssur ce s,v )= chemin} l'infinis'iln'existepas de cheminde s à v

26Heike Ripphausen-Lipa& Jean-Michel Adam

Propriétésdu parcoursenlargeur

Considéronsl'informationdistcalculéependant le parcours.

On a :dist(v) =įs,v)

C'est-à-dire que le parcours en largeur détermine les distances les plus courtes entre le sommet de départ et tous les autres sommets Les chemins les plus courts peuvent être déterminés à l'aide de l'information pred La preuvede cettepropriétépeutêtretrouvéedansle livre :

Algorithmique -3ème édition

Thomas H. Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein Cours avec 957 exercices et 158 problèmes -Dunodjuin 2010

27Heike Ripphausen-Lipa& Jean-Michel Adam

Propriétésde l'arbrede

parcoursenlargeur

Les cheminsde l'arbrede parcoursen

largeurde sversles autressommets, sontlesquotesdbs_dbs45.pdfusesText_45