GraphesLes différents parcours
Dans cette partie du cours nous allons nous interesser aux différents parcours d'un graphe :
- parcours en largeur d'abord
- parcours en profondeur d'abord
Parcours en largeur
Pour parcourir un graphe ou un arbre en utilisant l'algorithme de parcours en largeur (ou BFS, pour Breadth-First Search en anglais) on commence par explorer un noeud source, puis tous ses successeurs. Une fois qu'on a découvert tous les successeurs, on choisit un des successeur puis les successeurs non explorés des successeurs ...
Autrement dit, on commence d'abord par aller sur la plus grande largeur possible.
Principe
Son implémentation repose sur une
- 1 - Initialisation Creer une file et on emfile le sommet de départ ;
- 2 - Défiler un sommet pour le traiter ;
- 3 - Mettre tous ses voisins non explorés dans la file ;
- 4 - Si la file n'est pas vide reprendre à l'étape 2.
Première exemple:
graphe = {
"A": ["B","C"],
"B":["A", "C", "E"],
"C":["A", "B", "D"],
"D":["C"],
"E":["B"],
},
On initialise la file avec le sommet sélectionné c'est à dire le sommet B.
Place = aucun
File = B
Parcours = B
On défile B et on la place dans la parcours.
Comme B a qui ne sont ni dans la file ni dans le parcours, on les ajoutes.
Place = B
File = A - C - E
Parcours = B
On defile A et on le place dans le parcours.
Comme A n'as pas de voisins autre que B et C, on passe au suivant.
Place = A
File = C - E
Parcours = B - A
On defile C et on le place dans le parcours.
Comme C a qui ne sont ni dans la file ni dans le parcours, on les ajoutes. (ici le sommet D).
Place = A
File = E - D
Parcours = B - A - C
On defile E et on le place dans le parcours.
Comme tous les voisins de E ont été visités, on passe au suivant.
Place = E
File = D
Parcours = B - A - C - E
On defile D et on le place dans le parcours.
Comme tous les voisins de D ont été visités et que la file est vide, l'algorithme se termine.
Place = D
File = vide
Parcours = B - A - C - E - D
2nd exemple
Cette fois-ci, nous allons étudier les parcours du graphe ci-contre en commençant du sommet D.
graphe = {
"A":["B","C","E"],
"B":["A","D","F"],
"C":["A","E","F","G"],
"D":["B"],
"E":["A","C","G"],
"F":["B","E"],
"G":["C","E"],
}`
Le parcours est donc : D - B - A - F - C - E - G
Exercice :
On considère le graphe ci-dessous:
graphe = {
"A":["C","E","F"],
"B":["D","F"],
"C":["A","C","G","E"],
"D":["B"],
"E":["A","G","C"],
"F":["A","B","E"],
"G":["C","E"],
}`
Quel sera le parcours en profondeur commençant par le sommet D du graphe ci-dessus ?
*On supposera qu'au moment du choix, on prendra les sommets dans l'ordre alphabetique et on sépare les différents sommets par des - sans espace entre les noms des sommets (par exemple : A-B-G-D)
Parcours en profondeur
Pour parcourir un graphe ou un arbre en utilisant l'algorithme de parcours en profondeur (ou DFS pour Depth-First Search en anglais), on commence avec un nœud donné et on explore chaque branche complètement avant de passer à la suivante.
Autrement dit, on commence d'abord par aller le plus profond possible.
Principe
Voici la description intuitive de l'algorithme :
- Intialisation Creer une pile vide et empiler le sommet de départ
- Si le sommet de la pile possède des voisins qui n'ont pas été déjà visités, alors on sélectionne l'un de ces voisins et on l'empile et on le marque comme étant déjà visité ;
- Sinon on dépile (c'est-à-dire on supprime l'élément au sommet de la pile) ;
- On recommence au point 2 tant que la pile n'est pas vide ;
Première exemple:
"A": ["B","C"],
"B":["A", "C", "E"],
"C":["A", "B", "D"],
"D":["C"],
"E":["B"],
"F":["C"]
}, 
On initialise la pile avec le sommet sélectionné c'est à dire le sommet B.
Sommets visités = du début de la file
Pile = B
Parcours = Vide
On se place en B.
Sommets visités = B
Pile = B
Parcours = Vide
On se place en B.
Comme B a des voisins non visités, on sélectionne un sommet parmis ces voisins (ici le sommet A).
Sommets visités = B - A
Pile = A
B
Parcours = Vide
On se place en A.
Comme A a des voisins non visités, on sélectionne un sommet parmis ces voisins (ici le sommet C).
Sommets visités = B - A - C
Pile = C
A
B
Parcours = Vide
On se place en C.
Comme C a des voisins non visités, on sélectionne un sommet parmis ces voisins (ici le sommet D).
Sommets visités = B - A - C - D
Pile = D
C
A
B
Parcours = Vide
On se place en D.
Comme tous les voisins de D ont été visités, on dépile D et on le place dans le parcours.
Sommets visités = B - A - C - D
Pile = C
A
B
Parcours = D
On se place en C.
Comme C a des voisins non visités, on sélectionne un sommet parmis ces voisins (ici le sommet F).
Sommets visités = B - A - C - D - F
Pile = F
C
A
B
Parcours = D
On se place en F.
Comme tous les voisins de F ont été visités, on dépile F et on le place dans le parcours.
Sommets visités = B - A - C - D - F
Pile = C
A
B
Parcours = D - F
On se place en C.
Comme tous les voisins de C ont été visités, on dépile C et on le place dans le parcours.
Sommets visités = B - A - C - D - F
Pile = A
B
Parcours = D - F -C
On se place en A.
Comme tous les voisins de A ont été visités, on dépile A et on le place dans le parcours
Sommets visités = B - A - C - D - F
Pile = B
B
Parcours = D - F - C - A
On se place en B.
Comme B a encore un voisin non visité, on le sélectionne (ici le sommet E).
Sommets visités = B - A - C - D - F - E
Pile = E
B
Parcours = D - F - C - A
On se place en E.
Comme tous les voisins de E ont été visités, on dépile E et on le place dans le parcours.
Sommets visités = B - A - C - D - F - E
Pile = B
Parcours = D - F - C - A - E
On se place en B.
Comme tous les voisins de A ont été visités, on dépile B et on le place dans le parcours.
Sommets visités = B - A - C - D - F - E
Pile = Vide
Parcours = D - F - C - A - E - B
2nd exemple
Cette fois-ci, nous allons étudier les parcours du graphe ci-contre en commençant du sommet D.
graphe = {
"A":["B","C","E"],
"B":["A","D","F"],
"C":["A","C","G"],
"D":["B"],
"E":["A"],
"F":["B","E"],
"G":["C"],
}`
Le parcours est donc : G - C - E - A - F - B - D
Exercice :
On considère le graphe ci-dessous:
graphe = {
"A":["C","E","F"],
"B":["D","F"],
"C":["A","C","G","E"],
"D":["B"],
"E":["A","G","C"],
"F":["A","B","E"],
"G":["C","E"],
}`
Quel sera le parcours en profondeur commençant par le sommet D du graphe ci-dessus ?
*On supposera qu'au moment du choix, on prendra les sommets dans l'ordre alphabetique et on sépare les différents sommets par des - sans espace entre les noms des sommets (par exemple : A-B-G-D)