Matière : Théorie des graphes
Enseignante : Olfa Layouni
Année universitaire
2020/2021
Algorithmes de parcours d’un graphe
◼ On appelle exploration ou parcours d’un graphe, tout procédé déterministe qui permet
de choisir, à partir des sommets visités, le sommet suivant à visiter.
◼ Le problème consiste à déterminer un ordre sur les visites des sommets.
◼ Permet ainsi de calculer les distances de tous les nœuds depuis un nœud source dans
un graphe non valué (orienté ou non orienté).
◼ Il permet aussi de déterminer si un graphe est connexe ou non en basant le calcule sur
les composantes connexes du graphe
◼ Pour vérifier la connexité d’un graphe non orienté, il suffit pour cela d’appliquer un
des algorithmes suivants:
➢ Parcours en Largeur.
➢ Parcours en Profondeur.
◼ Ces parcours sont des algorithmes de marquage qui permettent d’explorer
complètement un graphe à partir d’un sommet quelconque
Algorithmes de connexités : Parcours en largeur (Breadth-First Search)
◼ Un parcours en largeur explore le graphe à partir d’un sommet donné (sommet de
départ ou sommet source).
◼ L’algorithme simule la transmission d’un message à partir d’un sommet source, en
utilisant l’idée suivante : tout sommet qui reçoit le message, le transférera à tous ses
voisins qui ne l’auront pas encore reçu.
◼ On continue avec le même principe jusqu’à visiter tous les sommets du graphe,
auquel cas le parcours est terminé ou bien reprend en un sommet non encore visité
◼ Pseudo-code:
void BFS (int debut) // début étant le sommet de départ{
enfiler (debut) ;
marquer[debut] = 1;
tant que (file non vide)
Année universitaire
2020/2021
Matière : Théorie des graphes
Enseignante : Olfa Layouni
{ s = defiler () ;
// traitement nécessaire sur le sommet s
pour tout w adjacent à s faire
si (Marque[w] == 0)
{
Marquer[w] = 1;
enfiler (w);
}
}}
Matière : Théorie des graphes
Enseignante : Olfa Layouni
Exemple:
Année universitaire
2020/2021
F
C
A
G
D
0
D
0
D
E
0
E
0
F
0
F
0
G
0
G
0
B
E
Exemple : BFS (A)
Marquer
A
0
B
0
C
0
SOMMET DE DEPART : A
A
1
B
0
C
0
ENFILER(A)
A
FILE F
DEFILER (A) // output A
B , D ET G sont les successeurs à A, selon l’ordre alphabétique enfiler(B) , enfiler(D),
enfiler(G)
Publicité
A
1
B
1
C
0
D
1
E
0
F
0
G
1
Matière : Théorie des graphes
Enseignante : Olfa Layouni
Année universitaire
2020/2021
D
B
G
File
2)
Defiler (B) // A B
F et E sont les successeurs de B, selon l’ordre alphabétique :
Enfiler (E)
A
1
Enfiler (F)
F
A
1
B
1
B
1
E
G
D
C
0
D
1
E
G
C
0
D
1
E
1
E
1
F
0
F
1
D
G
1
G
1
3) defiler(D)// output : A B D
C est le sommet adjacent à D
Enfiler(C)
Marquer
C
F
E
G
A
1
B
1
C
1
D
1
E
1
F
1
G
1
Année universitaire
2020/2021
E
F
F
Matière : Théorie des graphes
Enseignante : Olfa Layouni
Defiler(G) // output A B D G
E est déjà marqué et enfilé
Publicité
C
Defiler( E) // output : A B D G E
C
Defiler(F)// output: A B D G E F
C
C est adjacent à F marqué et enfilé
Defiler (C) // output AB D G E F C
File Vide
A
1
B
1
C
1
D
1
E
1
F
1
G
1
BFS(A) : AB D G E F C
Matière : Théorie des graphes
Enseignante : Olfa Layouni
Année universitaire
2020/2021
Exercise 1:
1) Parcourez en largeur le graphe en commençant le parcours à partir du nœud 4 : BFS(4)
4
0
4
1
5
0
5
0
6
0
6
0
7
0
7
0
4
8
0
8
0
Marquer :
1
0
2
0
3
0
Enfiler( 4) Marquer [4] :1
1
0
2
0
3
0
Defiler(4)
5 et 6 sont adjacents à 4
Enfiler( 5) Marquer [5] :1
Enfiler( 6) Marquer [6] :1
6
5
1
0
2
0
3
0
4
1
5
1
6
1
7
0
8
0
Matière : Théorie des graphes
Enseignante : Olfa Layouni
Année universitaire
2020/2021
Defiler(5)
7 et 8 sont adjacents à 5
Enfiler( 7) Marquer [7] :1
Publicité
Enfiler( 8) Marquer [8] :1
8
7
6
1
0
2
0
3
0
4
1
5
1
6
1
7
1
8
1
Defiler(6)
Defiler(7)
Defiler(8)
FIEL VIDE
BFS(4) : 4 5 6 7 8
2) Parcourez en largeur le graphe en commençant le parcours à partir du nœud 1 : BFS(1)
Marquer :
1
0
2
0
3
0
Enfiler(1) Marquer [1] :1
1
1
2
0
3
0
4
0
4
0
5
0
5
0
6
0
6
0
7
0
7
0
1
8
0
8
0
Matière : Théorie des graphes
Enseignante : Olfa Layouni
Année universitaire
2020/2021
Defiler(1)
2et 3 sont adjacents à 1
Enfiler( 2) Marquer [2] :1
Enfiler( 3) Marquer [3] :1
3
2
1
1
2
1
3
1
4
0
5
0
6
0
7
0
8
0
Defiler(2)
4 EST adjacents à 2
Enfiler( 4) Marquer [4] :1
4
1
1
Publicité
3
2
1
3
1
Defiler(3)
6 EST adjacents à 3
Enfiler( 6) Marquer [6] :1
6
1
1
4
2
1
3
1
Defiler(4)
5 ET 6 SONT adjacents à 4
Enfiler( 5) Marquer [5] :1
4
1
4
1
5
0
5
0
6
0
6
1
7
0
7
0
8
0
8
0
5
6
Matière : Théorie des graphes
Enseignante : Olfa Layouni
Année universitaire
2020/2021
1
1
2
1
3
1
4
1
5
1
6
1
7
0
8
0
Defiler (6)
Defiler(5)
7 et 8 sont adjacents à 5
Enfiler( 7) Marquer [7] :1
Enfiler( 8) Marquer [8] :1
8
7
1
1
2
1
3
1
4
1
5
1
6
1
7
1
8
1
Defiler(7)
Defiler(8)
FIEL VIDE
BFS(1) : 1 2 3 4 6 5 7 8