Algorithmes et implémentation en python sur un graphe
Nous allons commencer par nous intéresser aux algorithmes de parcours d'un graphe.
L'idée du "parcours" est de "visiter" tous les sommets d'un graphe en partant d'un sommet quelconque.
Ces algorithmes de parcours d'un graphe sont à la base de nombreux algorithmes très utilisés : routage des paquets de données dans un réseau, découverte du chemin le plus court pour aller d'une ville à une autre...
Il existe 2 méthodes pour parcourir un graphe :
- Le parcours en largeur
- le parcours en profondeur
1 - Parcours en largeur
Algorithme
Nous allons travailler sur un graphe G(V,E) avec V : l'ensemble des sommets de ce graphe et E : l'ensemble des arêtes de ce graphe.
Un sommet u sera adjacent avec un sommet v si u et v sont reliés par une arête (on pourra aussi dire que u et v sont voisins)
À chaque sommet u de ce graphe nous allons associer une couleur : blanc ou noir.
Autrement dit, chaque sommet u possède un attribut couleur que l'on notera u.couleur, nous aurons u.couleur = blanc ou u.couleur = noir.
Quelle est la signification de ces couleurs ?
- si u.couleur = blanc => u n'a pas encore été "découvert"
- si u.couleur = noir => u a été "découvert"
01°
Étudiez cet algorithme :
VARIABLE
G : un graphe
s : noeud (origine)
u : noeud
v : noeud
f : file (initialement vide)
//On part du principe que pour tout sommet u du graphe G, u.couleur = blanc à l'origine
DEBUT
s.couleur ← noir
enfiler (s,f)
tant que f non vide :
u ← defiler(f)
pour chaque sommet v adjacent au sommet u :
si v.couleur n'est pas noir :
v.couleur ← noir
enfiler(v,f)
fin si
fin pour
fin tant que
FIN
02°
Appliquez l'algorithme du parcours en largeur au graphe ci-dessous.
Le 'point de départ' de notre parcours (le sommet s dans l'algorithme), sera le sommet A.
Vous noterez les sommets atteints à chaque étape ainsi que les sommets présents dans la file f.
Vous pourrez aussi, à chaque étape, donner les changements de couleur des sommets.
Si vous trouvez l'exercice ci-dessus trop difficile, vous pouvez aussi vérifier que la "découverte" des sommets peut se faire dans l'ordre suivant : A, B, F, C, D, G, H, E et I (ce n'est pas la seule solution possible)
Vous avez sans doute remarqué que dans le cas d'un parcours en largeur, on "découvre" d'abord tous les sommets situés à une distance k du sommet "origine" (sommet s)
avant de commencer la découverte des sommets situés à une distance k+1
(on définit la distance comme étant le nombre d'arêtes à parcourir depuis A pour arriver à destination):
En effet, pour l'exemple de la question 2, nous avons bien :
| sommets | A | B | F | C | D | G | H | E | I |
| distances depuis A | 0 | 1 | 1 | 2 | 2 | 2 | 2 | 3 | 3 |
Implémentation en Python
On se propose d'implémenter en python, l'algorithme du parcours en largeur d'un graphe.
Pour cela, vous devez faire les différents exercices ci-dessous:
03°
Soit le graphe suivant :
Proposez une implémentation de ce graphe en Python (graphe 1 dans la suite)
Vous allez utiliser les listes d'adjacences dans un dictionnaire (fiche de cours précédente):
...CORRECTION...
#liste d'ajacence pour le graphe 1
graphe_1 = {
'A':['B','F'],
'B':['A', 'C', 'D', 'G'],
'C':['B', 'E'],
'D':['B', 'I'],
'E':['C', 'I'],
'F':['A', 'G', 'H'],
'G':['B', 'F', 'I'],
'H':['F', 'I'],
'I':['E', 'D', 'G', 'H']
}
04°
Soit l'algorithme de parcours en largeur vu précédement :
Implémentez cet algorithme en Python.
Vous utiliserer une fonction parcours_largeur(G, S) avec pour paramètre le graphe G et S le sommet de départ.
Vous testerez votre programme à l'aide du graphe 1.
Il faudra que votre programme fournisse la liste des sommets parcourus en partant du sommet A (il faudra être attentif à l'ordre des sommets dans cette liste)
...CORRECTION...
def parcours_largeur(G, S):
couleur = dict()
for cle in G :
couleur[cle] = 'blanc'
P = [] # liste des sommets visités
file = [S]
couleur[S] = 'noir'
while len(file) != 0 :
u = file.pop(0)
P.append(u)
for v in G[u]:
if couleur[v] != 'noir':
couleur[v] = 'noir'
file.append(v)
return P
2 - Parcours en profondeur
Algorithme
On va ici retrouver le même système de couleur (blanc : sommet non visité, noir : sommet déjà visité)
05°
Étudiez cet algorithme :
VARIABLE
G : un graphe
u : noeud
v : noeud
//On part du principe que pour tout sommet u du graphe G, u.couleur = blanc à l'origine
DEBUT
PARCOURS-PROFONDEUR(G,u) :
u.couleur ← noir
pour chaque sommet v adjacent au sommet u :
si v.couleur n'est pas noir :
PARCOURS-PROFONDEUR(G,v)
fin si
fin pour
FIN
Vous avez dû remarquer que le parcours en profondeur utilise une fonction récursive.
J'attire votre attention sur l'extrême simplicité de cet algorithme (au niveau de sa conception), c'est souvent le cas avec les algorithmes récursifs.
06°
Appliquez l'algorithme du parcours en profondeur d'abord au graphe ci-dessous.
Vous pourrez vérifier que la "découverte" des sommets peut se faire dans l'ordre suivant : A, B, C, E, I, D, G, F et H (ce n'est pas la seule solution possible)
07°
Comparez le résultat obtenu avec le parcours en largeur (A, B, F, C, D, G, H, E et I) et le résultat obtenu avec le parcours en profondeur (A, B, C, E, I, D, G, F et H)
Dans le cas du parcours en largeur on "découvrait" tous les sommets situés à une distance k de l'origine avant de s'intéresser aux sommets situés à une distance k+1 de l'origine. Dans le cas du parcours en profondeur, on va chercher à aller "le plus loin possible" dans le graphe : A -> B -> C -> E -> I -> D, quand on tombe sur "un cul-de-sac" (dans notre exemple, D est un "cul-de-sac", car une fois en D, on peut uniquement aller en B, or, B a déjà été découvert...), on revient "en arrière" (dans notre exemple, on repart de B pour aller explorer une autre branche : G -> F -> H)
À noter que l'utilisation d'un algorithme récursif n'est pas une obligation pour le parcours en profondeur :
08°
Étudiez cet algorithme :
VARIABLE
s : noeud (origine)
G : un graphe
u : noeud
v : noeud
p : pile (pile vide au départ)
//On part du principe que pour tout sommet u du graphe G, u.couleur = blanc à l'origine
DEBUT
s.couleur ← noir
piler(s,p)
tant que p n'est pas vide :
u ← depiler(p)
pour chaque sommet v adjacent au sommet u :
si v.couleur n'est pas noir :
v.couleur ← noir
piler(v,p)
fin si
fin pour
fin tant que
FIN
Vous avez sans doute remarqué que la version "non récursive" (on dit "itérative") de l'algorithme du parcours en profondeur ressemble beaucoup à l'algorithme du parcours en largeur.
On a juste remplacé la file par une pile.
09°
Appliquez l'algorithme du parcours en profondeur au graphe ci-dessous.
Vérifiez que l'on obtient bien un parcours en profondeur.
Implémentation en Python
10°
Soit l'algorithme de parcours en profondeur (version non récursive), vu ci-dessus:
Implémentez cet algorithme en Python.
Vous utiliserer une fonction parcours_profondeur(G, S) avec pour paramètre le graphe G et S le sommet de départ.
Vous testerez votre programme à l'aide du graphe 1.
Il faudra que votre programme fournisse la liste des sommets parcourus en partant du sommet A (il faudra être attentif à l'ordre des sommets dans cette liste)
...CORRECTION...
def parcours_profondeur(G, s):
couleur = dict()
for v in G :
couleur[v] = 'blanc'
P = [s] # liste des sommets visités
couleur[s]='noir'
pile = [s]
while len(pile) != 0 :
u = pile[-1]
voisin = [elt for elt in G[u] if couleur[elt] != 'noir']
if len(voisin) != 0 :
v = voisin[0]
couleur[v]='noir'
P.append(v)
pile.append(v)
else :
pile.pop()
couleur[u]='noir'
return P
11°
Soit l'algorithme de parcours en profondeur, vu ci-dessus(version récursive):
Implémentez cet algorithme en Python.
Vous utiliserer une fonction parcours_profondeur_rec(G, S) avec pour paramètre le graphe G et S le sommet de départ.
Vous testerez votre programme à l'aide du graphe 1.
Il faudra que votre programme fournisse la liste des sommets parcourus en partant du sommet A (il faudra être attentif à l'ordre des sommets dans cette liste)
...CORRECTION...
première version
def main(G, S):
P = [] # liste des sommets visités
couleur = dict()
for cle in G :
couleur[cle] = 'blanc'
def parcours_profondeur_rec(G, S):
couleur[S] = 'noir'
P.append(S)
for v in G[S]:
if couleur[v] != 'noir':
parcours_profondeur_rec(G, v)
return P
return parcours_profondeur_rec(G, S)
deuxième version
def parcours_profondeur_rec(G, S):
couleur[S] = 'noir'
P.append(S)
for v in G[S]:
if couleur[v] != 'noir':
parcours_profondeur_rec(G, v)
return P
def parcours(G, S):
global P, couleur
P = [] # liste des sommets visités
couleur = dict()
for cle in G :
couleur[cle] = 'blanc'
return parcours_profondeur_rec(G, S)
3 - Cycle dans les graphes
Voici un rappel de 2 définitions vues précédemment :
-
Une chaine est une suite d'arêtes consécutives dans un graphe, un peu comme si on se promenait sur le graphe.
On la désigne par les lettres des sommets qu'elle comporte.
On utilise le terme de chaine pour les graphes non orientés et le terme de chemin pour les graphes orientés. - Un cycle est une chaine qui commence et se termine au même sommet.
Pour différentes raisons, il peut être intéressant de détecter la présence d'un ou plusieurs cycles dans un graphe.
(par exemple pour savoir s'il est possible d'effectuer un parcours qui revient à son point de départ sans être obligé de faire demi-tour).
Algorithme
Nous allons étudier un algorithme qui permet de "détecter" la présence d'au moins un cycle dans un graphe :
12°
Étudiez cet algorithme. Que se passe-t-il quand le graphe G contient au moins un cycle ?
Que se passe-t-il quand le graphe G ne contient aucun cycle :
VARIABLE
s : noeud (noeud quelconque)
G : un graphe
u : noeud
v : noeud
p : pile (vide au départ)
//On part du principe que pour tout sommet u du graphe G, u.couleur = blanc à l'origine
DEBUT
CYCLE():
piler(s,p)
tant que p n'est pas vide :
u ← depiler(p)
pour chaque sommet v adjacent au sommet u :
si v.couleur n'est pas noir :
piler(v,p)
fin si
fin pour
si u est noir :
renvoie Vrai
sinon :
u.couleur ← noir
fin si
fin tant que
renvoie Faux
FIN
13°
Appliquez l'algorithme de détection d'un cycle au graphe ci-dessous (vous partirez du sommet de votre choix).
14°
Appliquez l'algorithme de détection d'un cycle au graphe ci-dessous (vous partirez du sommet de votre choix).
Chercher une chaine dans un graphe
Nous allons maintenant nous intéresser à un algorithme qui permet de trouver une chaine entre 2 sommets (sommet de départ et sommet d'arrivée). Les algorithmes de ce type ont une grande importance et sont très souvent utilisés (voir plus bas (après le "À faire vous-même 12") pour plus d'explications).
15°
Étudiez cet algorithme
VARIABLE
G : un graphe
start : noeud (noeud de départ)
end : noeud (noeud d'arrivé)
u : noeud
chaine : ensemble de noeuds (initialement vide)
DEBUT
TROUVE-CHAINE(G, start, end, chaine):
chaine = chaine ⋃ start //le symbol ⋃ signifie union, il permet d'ajouter le noeud start à l'ensemble chaine
si start est identique à end :
renvoie chaine
fin si
pour chaque sommet u adjacent au sommet start :
si u n'appartient pas à chaine :
nchemin = TROUVE-CHAINE(G, u, end, chaine)
si nchemin non vide :
renvoie nchemin
fin si
fin si
fin pour
renvoie NIL
FIN
Vous noterez que l'algorithme ci-dessus est basé sur un parcours en profondeur.
16°
Appliquez l'algorithme permettant de trouver une chaine entre un noeud de départ (start) et un noeud d'arrivée (end) au graphe ci-dessous (vous choisirez les noeuds de départ et d'arrivée de votre choix).
Il est important de noter que dans la plupart des cas, les algorithmes de recherche de chaine (ou de chemin), travaillent sur des graphes pondérés (par exemple pour rechercher la route entre un point de départ et un point d'arrivée dans un logiciel de cartographie). Ces algorithmes recherchent aussi souvent les chemins les plus courts (logiciels de cartographie).
On peut citer l'algorithme de Dijkstra ou encore l'algorithme de Bellman-Fordqui recherchent le chemin le plus court entre un noeud de départ et un noeud d'arrivée dans un graphe pondéré.
4 - FAQ
Algorithme de Dijkstra avec un graphe orienté
Activité publiée le 07 04 2021
modifié le 03 04 2023
Auteur : Andjekel
Sources : Pixees