26 - Graphe : parcours en largeur
Logiciel nécessaire pour l'activité : -
Prérequis :
- Données : les 3 activités sur les Graphes
- Algo : Parcours en largeur d'un Arbre
Evaluation ✎ : 01-02-03-08-09-10-11-12-13-14-15
1 - Rappel : parcours en largeur d'un arbre
Nous avons déjà vu la notion de parcours en largeur sur les arbres.
Le principe est
- d'explorer la racine de l'arbre puis
- d'explorer tous les noeuds à profondeur 1 de la racine.
- d'explorer tous les noeuds à profondeur 2 de la racine.
- ect... jusqu'à la plus grande profondeur
L'ordre de lecture des noeuds donne donc Alice - Bob - Clara - Didier - Eleonore...
L'algorithme consiste à :
- Enfiler l'arbre dans une file
- Tant que la file n'est pas vide
- Défiler le prochain arbre
- Explorer la racine de l'arbre
- Enfiler les enfants gauche et droite de cet arbre dans la file si ce ne sont pas des arbres vides.
2 - Parcours en largeur d'un graphe
2.1 Principe du parcours en largeur dans un graphe
Il s'agit du même principe avec un peu plus de subtilité dans l'exploration car on risque de retomber sur des sommets que nous avons déjà rencontré : il n'y a pas de notion de hiérarchie dans un graphe et il peut y avoir des cycles.
On commence par un sommet choisi (S5 ici).
On lit les sommets autour de ce premier sommet (S1 et S9).
On s'écarte encore d'un sommet autour (S2, S3 et S8)...
Cliquez sur l'image pour lancer l'animation.
Pour faire comprendre cela à un système informatique, nous allons utiliser les attributs suivants :
- un attribut couleur pour préciser l'état du sommet lors de l'exploration :
- BLANC : le sommet n'a pas encore été découvert lors de l'exploration
- GRIS : le sommet a été découvert
- NOIR : le sommet a été traité : on a exploré toutes ses arêtes ou ses arcs sortants. Tous ses sommets adjacents sont donc découverts (ils sont donc gris ou noir)
- un attribut distance qui contient le nombre d'arcs ou d'arêtes entre ce sommet et le sommet de départ. INFINI pour les sommets qui n'ont pas encore été découverts lors de l'exploration du graphe.
- un attribut parent qui contient le sommet depuis lequel on a découvert ce sommet. VIDE au départ de l'exploration. Seul le sommet de départ gardera cette valeur puisqu'il est le premier.
Voici l'algorithme en français :
- Pour chaque sommet u appartenant à l'ensemble S des sommets : on place BLANC dans couleur, on place INFINI dans distance, on place VIDE dans parent
- On choisit un sommet de départ qu'on peint en GRIS et qui possède une distance de 0.
- On enfile ce sommet de départ dans une file
- Tant que la file n'est pas vide
- on défile le prochain sommet qu'on nommera u
- pour chaque sommet v voisin / adjacent à u :
- Si v est BLANC
- ↦ On peint v en GRIS
- ↦ On définit la distance de v comme étant la distance de u + 1
- ↦ On définit le parent de v comme étant u
- ↦ On enfile v
- On peint u en NOIR puisqu'on a découvert tous ses sommets adjacents si on arrive ici
Point important : notez bien qu'on agit sur les sommets v uniquement s'ils sont blancs. On ne réalise donc qu'une unique fois par sommet les actions pointées par la flèche rouge ↦.
2.2 Exemple de déroulement de l'algorithme de parcours en largeur
On considère le graphe suivant en prenant le sommet 5 comme point de départ : on cherche donc à déterminer le nombre minimum d'arêtes entre ce sommet et n'importe quel autre sommet du graphe.
Etape initiale
On place donc une distance de 0 arête entre le sommet 5 et le sommet 5, logique. Les autres distances sont initialisées à l'infini.
On place le sommet 5 dans la file et on peut commencer.
Premier défilement
Comme la file n'est pas vide, on défile le sommet stocké dans la file. On obtient donc le sommet 5.
On fait le traitement voulu sur le sommet 5 puis on cherche dans sa matrice d'adjacence ou sa liste d'adjacence les sommets adjacents à ce sommet 5.
Imaginons qu'on obtienne la liste S1 - S9.
Deux séquences en boucle à faire :
- Puisque le sommet S1 est BLANC, on le peint en GRIS, on stocke que son parent est S5 et que la distance jusqu'à S1 est donc de 0+1, soit 1. Dernière étape : on enfile S1.
- Puisque le sommet S9 est BLANC, on le peint en GRIS, on stocke que son parent est S5 et que la distance jusqu'à S9 est donc de 0+1, soit 1. Dernière étape : on enfile S9.
Nous avons fini d'explorer toutes les arêtes partant du sommet S5 : on le peint en NOIR pour indiquer que nous avons totalement fini son traitement.
Deuxième défilement
Comme la file n'est pas vide, on défile le sommet stocké dans la file. On obtient donc le sommet 1.
On fait le traitement voulu sur le sommet 1 puis on cherche dans sa matrice d'adjacence ou sa liste d'adjacence les sommets adjacents à ce sommet 1.
Imaginons qu'on obtienne la liste S2 - S3 - S5.
Trois séquences en boucle à faire :
- Puisque le sommet S2 est BLANC, on le peint en GRIS, on stocke que son parent est S1 et que la distance jusqu'à S5 est donc de 1+1, soit 2. Dernière étape : on enfile S2.
- Puisque le sommet S3 est BLANC, on le peint en GRIS, on stocke que son parent est S1 et que la distance jusqu'à S5 est donc de 1+1, soit 2. Dernière étape : on enfile S3.
- Puisque le sommet S5 n'est plus BLANC, on ne fait rien.
Nous avons fini d'explorer toutes les arêtes partant du sommet S1 : on le peint en NOIR pour indiquer que nous avons totalement fini son traitement.
Troisième défilement
Comme la file n'est pas vide, on défile le sommet stocké dans la file. On obtient donc le sommet 9.
On fait le traitement voulu sur le sommet 9 puis on cherche dans sa matrice d'adjacence ou sa liste d'adjacence les sommets adjacents à ce sommet 9.
Imaginons qu'on obtienne la liste S5 - S8.
Deux séquences en boucle à faire :
- Puisque le sommet S5 n'est plus BLANC, on ne fait rien.
- Puisque le sommet S8 est BLANC, on le peint en GRIS, on stocke que son parent est S9 et que la distance jusqu'à S5 est donc de 1+1, soit 2. Dernière étape : on enfile S8.
Nous avons fini d'explorer toutes les arêtes partant du sommet S9 : on le peint en NOIR pour indiquer que nous avons totalement fini son traitement.
Quatrième défilement
Comme la file n'est pas vide, on défile le sommet stocké dans la file. On obtient donc le sommet 2.
On fait le traitement voulu sur le sommet 2 puis on cherche dans sa matrice d'adjacence ou sa liste d'adjacence les sommets adjacents à ce sommet 2. Remarquez bien qu'on passe à cette distance car il n'existe plus de sommet directement adjacent à S5.
Imaginons qu'on obtienne la liste S1 - S3 - S4 - S6.
Quatre séquences en boucle à faire :
- Puisque le sommet S1 n'est plus BLANC, on ne fait rien.
- Puisque le sommet S3 n'est plus BLANC, on ne fait rien.
- Puisque le sommet S4 est BLANC, on le peint en GRIS, on stocke que son parent est S2 et que la distance jusqu'à S5 est donc de 2+1, soit 3. Dernière étape : on enfile S4.
- Puisque le sommet S6 est BLANC, on le peint en GRIS, on stocke que son parent est S2 et que la distance jusqu'à S5 est donc de 2+1, soit 3. Dernière étape : on enfile S6.
Nous avons fini d'explorer toutes les arêtes partant du sommet S2 : on le peint en NOIR pour indiquer que nous avons totalement fini son traitement.
Normalement... vous avez compris le principe.
Cinquième défilement
Sixième défilement
Septième défilement
Huitième défilement
Neuvième défilement
A partir de là, toutes les arêtes de tous les sommets ont été explorées. Nous avons donc parcouru l'intégralité du graphe.
On obtient au final :
- Un Arbre dont la racine est le sommet de départ et qui mène à tous les autres sommets : cela permet de connaître UN chemin entre le sommet de départ et les autres.
- La distance minimale en nombre d'arêtes entre le sommet de départ et n'importe quel autre sommet.
3.3 Questions de compréhension
✎ 01° Sur l'Arbre de parcours obtenu, quel est l'enchaînement de sommets obtenu pour aller du sommet S5 au sommet S6 ?
✎ 02° Compter le nombre d'arêtes utilisées pour aller de S5 à S6. Obtient-on bien une distance de 3 comme indiqué au dessus du sommet 6 sur le graphe ?
✎ 03° Pourquoi la distance indiquée pour S5 sur le graphe est-elle de 0 ?
04° On utilise une fois chaque sommet comme centre de recherches. Combien de fois utilise-t-on les arêtes ?
- On utilise une fois chaque arête
- On utilise deux fois chaque arête
- On utilise trois fois chaque arête
- J'aime ni les arêtes, ni le poisson
...CORRECTION...
On utilise les arêtes dans les deux sens. Donc deux fois.
05° Nous allons chercher la complexité de cet algorithme en prenant comme référence le nombre de fois où on teste si un sommet est BLANC. On considère uniquement un graphe connexe. Notons a le nombre d'arêtes. La complexité de cet algorithme est :
- Logarithmique en fonction de a ?
- Linéaire en fonction de a ?
- Quadratique en fonction de a ?
- Exponentielle en fonction de a ?
...CORRECTION...
Puisqu'on utilise deux fois les arêtes, on peut noter 𝞗(2a). Comme on ne s'intéresse pas au facteur multiplicatif, on obtient donc 𝞗(a). La bonne réponse est donc linéaire.
Le coût total d'exécution dépend en réalité du nombre de sommets et du nombre d'arêtes. Par contre, si le graphe n'est pas connexe, on peut très bien ne pas rencontrer ni traiter certains sommets et certains arcs ou arêtes.
On peut donc écrire 𝞞(s+a)
06° Donner deux chemins de distance 3 allant de S5 à S6. Quel est le parent unique de S6 sur l'Arbre de parcours obtenu ? En déduire le chemin qui va être choisi ici si on suit l'Arbre de parcours.
...CORRECTION...
S5-S1-S2-S6 ou S5-S9-S8-S6.
On voit sur l'Arbre qu'on obtiendrait ici le premier choix car le parent de S6 est S2.
Le parent de S2 est S1.
Le parent de S1 est S5.
07° Peut-on trouver un chemin de moins de 3 arêtes menant de S5 à S6 ?
...CORRECTION...
Non : le parcours en largeur donne 3. Il n'y a donc pas de chemin plus court que 3 arêtes.
Voici en image le graphe final obtenu :
Dans une activité pratique de programmation, nous verrons comment utiliser cela pour trouver automatiquement la sortie la plus proche en nombre de cases dans un labyrinthe par exemple.
3 - Algorithme de parcours en largeur
Algorithme du parcours en largeur
ENTREES
- Un graphe noté g
- Un sommet qui servira de sommet origine, noté s appartenant au graphe g
SORTIE
Aucune ici mais on peut facilement modifier l'algorithme pour qu'il renvoie par exemple l'Arbre de parcours.
ALGORITHME PARCOURS EN LARGEUR
on initialise tous les sommets
POUR chaque sommet u appartenant au graphe g
u.couleur ← BLANC
u.distance ← INFINI
u.parent ← VIDE
Fin Pour
on initialise le sommet origine
s.couleur ← GRIS
s.distance ← 0
s.parent ← VIDE
on crée la file et on y place le sommet origine
a_traiter ← nouvelleFileVide()
enfiler(a_traiter, s)
on sort et active un sommet à la fois de la file
TANT QUE NON estVide(a_traiter)
u ← defiler(a_traiter)
POUR chaque sommet v appartenant à la liste d'adjacence du sommet u
SI v.couleur est BLANC
si on arrive ici, c'est que le sommet n'a pas encore été découvert
v.couleur ← GRIS
v.distance ← u.distance + 1
v.parent ← u
enfiler(a_traiter, v)
Fin Si
u.couleur ← NOIR
Fin Pour
Fin Tant Que
Renvoyer VIDE (∅)
4 - Exercices
Maintenant que vous avez vu l'exécution une première fois et que vous avez vu l'algorithme, il est temps de vous l'approprier.
Nous l'utiliserons dans le cadre d'un mini-projet on nous tenterons de faire sortir un personnage d'un labyrinthe, alors que des monstres rodent...
✎ 08° Fournir les listes d'adjacence des sommets ci-dessous. On placera toujours les sommets dans l'ordre alphabétique.
✎ 09° Fournir l'arbre de parcours obtenu à partir du sommet c.
✎ 10° Fournir les listes des successeurs des sommets ci-dessous. On placera toujours les sommets dans l'ordre alphabétique. Attention, cette fois le graphe est orienté.
✎ 11° Fournir l'arbre de parcours obtenu à partir du sommet c. Il faudra bien entendu ne prendre que la liste des successeurs.
✎ 12° Fournir l'arbre de parcours obtenu à partir du sommet a.
✎ 13° Fournir l'arbre de parcours obtenu à partir du sommet d.
✎ 14° Quel semble être le sommet le plus central ?
✎ 15° Le parcours en largeur fonctionne pour trouver le plus court chemin dans un graphe orienté non pondéré. Expliquez pourquoi il ne fonctionne pas pour un graphe pondéré, où le poids des arcs ou des arêtes n'est pas nécessairement 1 ?
5 - FAQ
Et on fait comment sur un graphe pondéré ?
On applique l'algorithme de Dijkstra.
Et avec un traitement naïf en Python, ça donne quoi ?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118 |
|
Voici le résultat du programme de test précédent :
Graphe en tant que dictionnaire :
{0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3]}
Résultat du parcours en largeur d'abord
(0, {'couleur': 2, 'distance': 0, 'parent': None})
(1, {'couleur': 2, 'distance': 1, 'parent': 0})
(2, {'couleur': 2, 'distance': 1, 'parent': 0})
(3, {'couleur': 2, 'distance': 2, 'parent': 1})
(4, {'couleur': 2, 'distance': 3, 'parent': 3})
Recherche du chemin entre 0 et 3
[0, 1, 3]
Et avec un bon traitement en Python, ça donne quoi ?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88 |
|
Activité publiée le 29 04 2021
Dernière modification : 29 04 2021
Auteur : ows. h.