[PDF] Parcours dun graphe - Claude Bernard University Lyon 1

Parcours dun graphe - Claude Bernard University Lyon 1

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

Si le graphe est donné par tableau de listes de successeurs, la complexité du parcours en largeur est O(n+ m) 2 1 3 Exercices 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

Algorithmique — M1 TD 2 : Parcours de Graphes

Exercice 1 : Appliquer a ce graphe l’algorithme de parcours en largeur (le sommet origine est indiqu´e par une simple fl`eche entrante) L’arbre de parcours en largeur r´esultant sera pr´esent´e par un sch´ema dans lequel les sommets de profondeur ´egale seront mis a la mˆeme hauteur, le sommet origine ´etant mis en haut

Parcours de graphes - miashs-wwwu-gafr

Propriétés de l’arbre de parcours en largeur Les chemins de l’arbre de parcours en largeur de s vers les autres sommets, sont les chemins les plus courts (en nombre d’arêtes) dans le graphe G, de s vers tous les autres sommets Heike Ripphausen -Lipa & Jean-Michel Adam 28

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

Algorithmes et structures de données génériques

5 6 6 Parcours en profondeur (matrices) 285 5 6 7 Parcours en largeur (matrices) 285 5 6 8 Plus courts chemins entre tous les sommets (Floyd) 286 5 6 9 Algorithme de Floyd 288 5 6 10 Algorithme de calcul de la fermeture transitive 290 5 6 11 Menu de test des graphes (matrices) 293 5 7 Résumé 293 5 8 Conclusion générale 294

INTELLIGENCE ARTIFICIELLE JI

niveau suivant Pour effectuer le parcours en largeur, une file est utilisée Le parcours s’arrête quand un état final est trouvé ou quand une profon-deur maximale est atteinte Ce parcours est très cher en temps et en espace mais il garantit de trouver la solution si elle existe; tandis que le parcours

[PDF] algorithme de parcours en profondeur en c PDF Cours,Exercices ,Examens

[PDF] Algorithme de Pythagore 2nde Mathématiques

[PDF] ALGORITHME DE PYTHAGORE ( TI-84 plus ) 2nde Mathématiques

[PDF] algorithme de recherche dans un tableau PDF Cours,Exercices ,Examens

[PDF] algorithme de recherche dichotomique PDF Cours,Exercices ,Examens

[PDF] algorithme de recherche intelligence artificielle PDF Cours,Exercices ,Examens

[PDF] algorithme de recherche python PDF Cours,Exercices ,Examens

[PDF] Algorithme de resolution d'equation de degré 1 ou 2 1ère Mathématiques

[PDF] Algorithme de seconde 2nde Mathématiques

[PDF] Algorithme de suite pour un devoir maison Terminale Mathématiques

[PDF] Algorithme de suites 1ère Mathématiques

[PDF] algorithme de tracé de cercle PDF Cours,Exercices ,Examens

[PDF] Algorithme de x en fonction de y 1ère Mathématiques

[PDF] algorithme débranché PDF Cours,Exercices ,Examens

[PDF] Algorithme dérivées 1ère Mathématiques

Parcours d'un graphe

ISN 2013

Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 1 / 97

Exercices a rendre

Trois exercices sont a rendre.L' exercice 1 pourra ^etre rendu sur papier mardi 2 avril (ou en version

electronique si vous preferez).Les exercices 2 et 3 sont a rendre dans les casiers numeriques de vos enseignants lundi 1 avril. Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 2 / 97

A savoir

A la suite de cette seance, vous devrezsavoirparcourir un graphe en profondeur et en largeur. Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 3 / 97

L'essentiel de la notion de graphe

On peut apprehender la notion de graphe par l'une de ses representations classiques : des points (sommets du graphe) et des courbes reliant certains de ces points (ar^etes du graphe).g ah bcde f1 2 34
56
7

891011

12 Les sommets de ce graphe sonta,b,c,d,e,f,g,h. Les sommetseetc sont adjacents (voisins) : ils sont en eet relies par l'ar^ete 10. Le sommet

ba pour voisinsh,fetc. Le sommetaest incident aux ar^etes 2 et 3.Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 4 / 97

L'essentiel de la notion de graphe

On peut apprehender la notion de graphe par l'une de ses representations classiques : des points (sommets du graphe) et des courbes reliant certains de ces points (ar^etes du graphe).g ah bcde f1 2 34
56
7

891011

12 Lorsqu'on passe d'un sommet a un autre en se deplacant le long d'ar^etes et de sommets, on dit que l'on denit un chemin dans le graphe. On peut par exemple denir le chemin g, 3, a, 2, h, 5, b, 7, f dans le graphe ci-dessus. Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 4 / 97

Exemples de situations modelisees par un graphe

Le web : chaque page est un sommet du graphe, chaque lien

hypertexte est une ar^ete entre deux sommets.Un reseau ferroviaire : chaque gare est un sommet, les voies entre

deux gares sont les ar^etes. Idem avec un reseau routier.Un reseau social : les sommets sont les personnes, deux personnes

sont adjacentes dans ce graphe lorsqu'elles sont \amies". Si la notion d'amitie n'est pas reciproque, le graphe est oriente. Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 5 / 97

Exemples de situations modelisees par un graphe

Le web : chaque page est un sommet du graphe, chaque lien

hypertexte est une ar^ete entre deux sommets.Un reseau ferroviaire : chaque gare est un sommet, les voies entre

deux gares sont les ar^etes. Idem avec un reseau routier.Un reseau social : les sommets sont les personnes, deux personnes

sont adjacentes dans ce graphe lorsqu'elles sont \amies". Si la notion d'amitie n'est pas reciproque, le graphe est oriente. Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 5 / 97

Exemples de situations modelisees par un graphe

Le web : chaque page est un sommet du graphe, chaque lien

hypertexte est une ar^ete entre deux sommets.Un reseau ferroviaire : chaque gare est un sommet, les voies entre

deux gares sont les ar^etes. Idem avec un reseau routier.Un reseau social : les sommets sont les personnes, deux personnes

sont adjacentes dans ce graphe lorsqu'elles sont \amies". Si la notion d'amitie n'est pas reciproque, le graphe est oriente. Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 5 / 97

Exemples de situations modelisees par un graphe

Le web : chaque page est un sommet du graphe, chaque lien

hypertexte est une ar^ete entre deux sommets.Un reseau ferroviaire : chaque gare est un sommet, les voies entre

deux gares sont les ar^etes. Idem avec un reseau routier.Un reseau social : les sommets sont les personnes, deux personnes

sont adjacentes dans ce graphe lorsqu'elles sont \amies". Si la notion d'amitie n'est pas reciproque, le graphe est oriente. Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 5 / 97

Exemples de situations modelisees par un graphe

Le web : chaque page est un sommet du graphe, chaque lien

hypertexte est une ar^ete entre deux sommets.Un reseau ferroviaire : chaque gare est un sommet, les voies entre

deux gares sont les ar^etes. Idem avec un reseau routier.Un reseau social : les sommets sont les personnes, deux personnes

sont adjacentes dans ce graphe lorsqu'elles sont \amies".

Si la notion d'amitie n'est pas reciproque, le graphe est oriente.La structure de graphe est en science de l'informatique une structure

abstraite omnipresente. Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 5 / 97

Representation informatique d'un graphe

Une structure theorique comme un graphe est susceptible de nombreuses

implementations, selon le type de problemes a resoudre.On peut par exemple utiliser la matrice d'adjacence du graphe.

ab cdef g h0 B

BBBBBBBBB@a b c d e f g h

a0 1 1 0 0 0 0 0 b1 0 0 1 1 0 0 0 c1 0 0 1 0 0 0 0 d0 1 1 0 1 0 0 0 e0 1 0 1 0 1 1 0 f0 0 0 0 1 0 1 0 g0 0 0 0 1 1 0 1 h0 0 0 0 0 0 1 01 C CCCCCCCCCAJean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 6 / 97

Representation informatique d'un graphe

Une structure theorique comme un graphe est susceptible de nombreuses

implementations, selon le type de problemes a resoudre.On peut par exemple utiliser la matrice d'adjacence du graphe.

ab cdef g h0 B

BBBBBBBBB@a b c d e f g h

a0 1 1 0 0 0 0 0 b1 0 0 1 1 0 0 0 c1 0 0 1 0 0 0 0 d0 1 1 0 1 0 0 0 e0 1 0 1 0 1 1 0 f0 0 0 0 1 0 1 0 g0 0 0 0 1 1 0 1 h0 0 0 0 0 0 1 01 C CCCCCCCCCAJean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 6 / 97 Exemple de codage : utilisation d'un dictionnaire python

Python

G=dict()

G['a']=['b','c']

G['b']=['a','d','e']

G['c']=['a','d']

G['d']=['b','c','e']

G['e']=['b','d','f','g']

G['f']=['e','g']

G['g']=['e','f','h']

G['h']=['g']ab

cdef g h Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 7 / 97

PILE et FILE

Les notions depileet defilesont deux structures de donnees abstraites importantes en informatique. On limite ci-dessous la presentation de ces notions aux besoins des parcours de graphes envisages ci-apres. Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 8 / 97

PILE (stack)

La structure depileest celle d'une pile d'assiettes :Pour ranger les assiettes, on les empile les unes sur les autres.

Lorsqu'on veut utiliser une assiette, c'est l'assiette qui a ete empilee en dernier qui est utilisee.

Structure LIFO (last in, rst out)

Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 9 / 97

FILE (queue)

La structure defileest celle d'une le d'attente a un guichet :Les nouvelles personnes qui arrivent se rangent a la n de la le

d'attente.La personne servie est celle qui est arrivee en premier dans la le.

Structure FIFO (rst in, rst out).

Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 10 / 97

Parcours de graphe

Parcours en largeur

Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 11 / 97

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.1Dans le parcours en largeur, on utilise une le. On enle le sommet de

depart (on visite la page index du site).2On visite les voisins de la t^ete de le (pages ciblees par la page de

t^ete de le). On les enle (en les numerotant au fur et a mesure de leur decouverte) s'ils ne sont pas deja presents dans la le, ni deja passes dans la le.3On dele (c'est a dire : on supprime la t^ete de le).

4On recommence au point 2 (tant que c'est possible, c'est a dire tant

que la le n'est pas vide). Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 12 / 97

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.1Dans le parcours en largeur, on utilise une le. On enle le sommet de

depart (on visite la page index du site).2On visite les voisins de la t^ete de le (pages ciblees par la page de

t^ete de le). On les enle (en les numerotant au fur et a mesure de leur decouverte) s'ils ne sont pas deja presents dans la le, ni deja passes dans la le.3On dele (c'est a dire : on supprime la t^ete de le).

4On recommence au point 2 (tant que c'est possible, c'est a dire tant

que la le n'est pas vide). Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 12 / 97

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.1Dans le parcours en largeur, on utilise une le. On enle le sommet de

depart (on visite la page index du site).2On visite les voisins de la t^ete de le (pages ciblees par la page de

t^ete de le). On les enle (en les numerotant au fur et a mesure de leur decouverte) s'ils ne sont pas deja presents dans la le, ni deja passes dans la le.3On dele (c'est a dire : on supprime la t^ete de le).

4On recommence au point 2 (tant que c'est possible, c'est a dire tant

que la le n'est pas vide). Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 12 / 97

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.1Dans le parcours en largeur, on utilise une le. On enle le sommet de

depart (on visite la page index du site).2On visite les voisins de la t^ete de le (pages ciblees par la page de

t^ete de le). On les enle (en les numerotant au fur et a mesure de leur decouverte) s'ils ne sont pas deja presents dans la le, ni deja passes dans la le.3On dele (c'est a dire : on supprime la t^ete de le).

4On recommence au point 2 (tant que c'est possible, c'est a dire tant

que la le n'est pas vide). Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 12 / 97

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.1Dans le parcours en largeur, on utilise une le. On enle le sommet de

depart (on visite la page index du site).2On visite les voisins de la t^ete de le (pages ciblees par la page de

t^ete de le). On les enle (en les numerotant au fur et a mesure de leur decouverte) s'ils ne sont pas deja presents dans la le, ni deja passes dans la le.3On dele (c'est a dire : on supprime la t^ete de le).

4On recommence au point 2 (tant que c'est possible, c'est a dire tant

que la le n'est pas vide). Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 12 / 97

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.1Dans le parcours en largeur, on utilise une le. On enle le sommet de

depart (on visite la page index du site).2On visite les voisins de la t^ete de le (pages ciblees par la page de

t^ete de le). On les enle (en les numerotant au fur et a mesure de leur decouverte) s'ils ne sont pas deja presents dans la le, ni deja passes dans la le.3On dele (c'est a dire : on supprime la t^ete de le).

4On recommence au point 2 (tant que c'est possible, c'est a dire tant

que la le n'est pas vide).En d'autres termes, on traite toujours en priorite les liens des pages le plus

t^ot decouvertes. Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 12 / 97

Parcours en largeur d'un arbre

Parcourir en largeur le graphe ci-dessous a partir du sommet s :s Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 13 / 97

Parcours en largeur d'un arbre1

Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 14 / 97

Parcours en largeur d'un arbre1

2 56
11123
7894
10 1314

Enler : passage en gris. Deler : passage en noir.

L'ordre pour enler les voisins (ni gris, ni noirs) depend de l'implantation. Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 15 / 97

Parcours en largeur d'un arbre1

2 56
11123
7894
10 1314
Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 16 / 97

Parcours en largeur d'un arbre1

2 56
11123
7894
10 1314
Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 17 / 97

Parcours en largeur d'un arbre1

2 56
11123
7894
10 1314
Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 18 / 97

Parcours en largeur d'un arbre1

2 56
11123
7894
10 1314
Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 19 / 97

Parcours en largeur d'un arbre1

2 56
11123
7894
10 1314
Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 20 / 97

Parcours en largeur d'un arbre1

2 56
11123
7894
10 1314
Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 21 / 97

Parcours en largeur d'un arbre1

2 56
11123
7894
10 1314
Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 22 / 97

Parcours en largeur d'un arbre1

2 56
11123
7894
10 1314
Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 23 / 97

Parcours en largeur d'un arbre1

2 56
11123
7894
10 1314
Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 24 / 97

Parcours en largeur d'un arbre1

2 56
11123
7894
10 1314
Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 25 / 97

Parcours en largeur d'un arbre1

2 56
11123
7894
10 1314
Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 26 / 97

Parcours en largeur d'un arbre1

2 56
11123
7894
10 1314
Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 27 / 97

Parcours en largeur d'un arbre1

2 56
11123
7894
10 1314
Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 28 / 97

Parcours en largeur : une propriete

Une facon de comprendre l'algorithme est d'utiliser une notion de distance :une page est a distance 1 de la page de depart si on l'atteint par un

lien direct depuis la page 1,elle est a distance 2 de la page de depart si on peut l'atteindre (par le

plus court chemin) en passant par une page a distance 1 du depart,elle est a distance 3 du depart si on peut l'atteindre (par le plus court

chemin) en passant par une page a distance 1 et une page a distance 2... Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 29 / 97

Parcours en largeur : une propriete

Une facon de comprendre l'algorithme est d'utiliser une notion de distance :une page est a distance 1 de la page de depart si on l'atteint par un

lien direct depuis la page 1,elle est a distance 2 de la page de depart si on peut l'atteindre (par le

plus court chemin) en passant par une page a distance 1 du depart,elle est a distance 3 du depart si on peut l'atteindre (par le plus court

chemin) en passant par une page a distance 1 et une page a distance 2... Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 29 / 97

Parcours en largeur : une propriete

Une facon de comprendre l'algorithme est d'utiliser une notion de distance :une page est a distance 1 de la page de depart si on l'atteint par un

lien direct depuis la page 1,elle est a distance 2 de la page de depart si on peut l'atteindre (par le

plus court chemin) en passant par une page a distance 1 du depart,elle est a distance 3 du depart si on peut l'atteindre (par le plus court

chemin) en passant par une page a distance 1 et une page a distance 2... Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 29 / 97

Parcours en largeur : une propriete

Une facon de comprendre l'algorithme est d'utiliser une notion de distance :une page est a distance 1 de la page de depart si on l'atteint par un

lien direct depuis la page 1,elle est a distance 2 de la page de depart si on peut l'atteindre (par le

plus court chemin) en passant par une page a distance 1 du depart,elle est a distance 3 du depart si on peut l'atteindre (par le plus court

chemin) en passant par une page a distance 1 et une page a distance 2... Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 29 / 97

Parcours en largeur : une propriete

Une facon de comprendre l'algorithme est d'utiliser une notion de distance :une page est a distance 1 de la page de depart si on l'atteint par un

lien direct depuis la page 1,elle est a distance 2 de la page de depart si on peut l'atteindre (par le

plus court chemin) en passant par une page a distance 1 du depart,elle est a distance 3 du depart si on peut l'atteindre (par le plus court

chemin) en passant par une page a distance 1 et une page a distance

2...L'algorithme de parcours en largeur va visiter en premier lieu toutes les

pages a distance 1 du depart, puis toutes les pages a distance 2 du depart, puis toutes les pages a distance 3...(c'est en fait cette propriete qui donne son nom a ce type de parcours). Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 29 / 97

BFS (breadth rst search) : programmation python

Exercice avec corrige.

Avec la representation d'un graphe par un dictionnaire comme precedemment, programmer en langage python le BFS avec les variables suivantes :Un dictionnaire P. En n de parcours, pour tout sommet s du graphe P[s] sera le pere de s, c'est a dire le sommet a partir duquel le

sommet s a ete decouvert lors du parcours.Un dictionnaire couleur. Pour tout sommet s, couleur[s] vaut blanc si

le sommet s n'est pas passe dans la le, gris s'il est dans la le, noir lorsqu'il est sorti de la le.Une liste Q utilisee comme le (fo) : on enle un sommet lorsqu'il est decouvert, on le dele lorsqu'il est termine (traitement prioritaire des sommets decouverts au plus t^ot). Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 30 / 97

BFS (breadth rst search) : programmation python

Exercice avec corrige.

Avec la representation d'un graphe par un dictionnaire comme precedemment, programmer en langage python le BFS avec les variables suivantes :Un dictionnaire P. En n de parcours, pour tout sommet s du graphe P[s] sera le pere de s, c'est a dire le sommet a partir duquel le

sommet s a ete decouvert lors du parcours.Un dictionnaire couleur. Pour tout sommet s, couleur[s] vaut blanc si

le sommet s n'est pas passe dans la le, gris s'il est dans la le, noir lorsqu'il est sorti de la le.Une liste Q utilisee comme le (fo) : on enle un sommet lorsqu'il est decouvert, on le dele lorsqu'il est termine (traitement prioritaire des sommets decouverts au plus t^ot). Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 30 / 97

BFS (breadth rst search) : programmation python

Exercice avec corrige.

Avec la representation d'un graphe par un dictionnaire comme precedemment, programmer en langage python le BFS avec les variables suivantes :Un dictionnaire P. En n de parcours, pour tout sommet s du graphe P[s] sera le pere de s, c'est a dire le sommet a partir duquel le

sommet s a ete decouvert lors du parcours.Un dictionnaire couleur. Pour tout sommet s, couleur[s] vaut blanc si

le sommet s n'est pas passe dans la le, gris s'il est dans la le, noir lorsqu'il est sorti de la le.Une liste Q utilisee comme le (fo) : on enle un sommet lorsqu'il est decouvert, on le dele lorsqu'il est termine (traitement prioritaire des sommets decouverts au plus t^ot). Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 30 / 97

BFS (breadth rst search) : programmation python

Exercice avec corrige.

Avec la representation d'un graphe par un dictionnaire comme precedemment, programmer en langage python le BFS avec les variables suivantes :Un dictionnaire P. En n de parcours, pour tout sommet s du graphe P[s] sera le pere de s, c'est a dire le sommet a partir duquel le

sommet s a ete decouvert lors du parcours.Un dictionnaire couleur. Pour tout sommet s, couleur[s] vaut blanc si

le sommet s n'est pas passe dans la le, gris s'il est dans la le, noir lorsqu'il est sorti de la le.Une liste Q utilisee comme le (fo) : on enle un sommet lorsqu'il est decouvert, on le dele lorsqu'il est termine (traitement prioritaire des sommets decouverts au plus t^ot). Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 30 / 97

Exemple d'execution

Deroulement attendu du programme, avec l'appel bfs(G,'b'), sur le graphe ci-dessous :Python

G=dict()

G['a']=['b','c']

G['b']=['a','d','e']

G['c']=['a','d']

G['d']=['b','c','e']

G['e']=['b','d','f','g']

G['f']=['e','g']

G['g']=['e','f','h']

G['h']=['g']ab

cdef g h Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 31 / 97

Deroulement

ab cdef g h

P=f'b' : Noneg

Q=['b']

Decouverts (gris ou noirs) =['b']

Fermes (noirs) =[]

Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 32 / 97

Deroulement

ab cdef g h

P=f'b' : None, 'a' :'b', 'd' :'b', 'e' :'b'g

Q=['b','a','d','e']

Decouverts =['b','a','d','e']

Fermes=[]

Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 33 / 97

Deroulement

ab cdef g h

P=f'b' : None, 'a' :'b', 'd' :'b', 'e' :'b'g

Q=['a','d','e']

Decouverts=['b','a','d','e']

Fermes=['b']

Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 34 / 97

Deroulement

ab cdef g h P=f'b' : None, 'a' :'b', 'd' :'b', 'e' :'b','c' :'a'g

Q=['d','e','c']

Decouverts=['b','a','d','e','c']

Fermes=['b','a']

Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 35 / 97

Deroulement

ab cdef g h P=f'b' : None, 'a' :'b', 'd' :'b', 'e' :'b','c' :'a'g

Q=['e','c']

Decouverts=['b','a','d','e','c']

Fermes=['b','a','d']

Jean-Manuel Meny { IREM de LYON ()AlgorithmiqueISN 2013 36 / 97

Deroulement

abquotesdbs_dbs5.pdfusesText_10