Lycée > Terminale > NSI > Se déplacer dans un graphe

Se déplacer dans un graphe

Fiche de cours
Quiz
Profs en ligne
Videos
Application mobile

Objectifs

Parcourir un graphe en profondeur d’abord.
Parcourir un graphe en largeur d’abord.
Chercher des chemins dans un graphe entre deux sommets.

Points clés

Le parcours en profondeur d’abord d’un graphe détermine tous les nœuds accessibles à partir d’un sommet donné.
Le parcours en largeur d’abord d’un graphe explore les nœuds du graphe en les classant du plus proche au plus éloigné.

Pour bien comprendre

Comprendre la structure hiérarchique de graphe.
Savoir implémenter un graphe.
Comprendre la structure de données file.

1. Le parcours en profondeur d’abord

a. Principe

Parcourir un graphe, c’est lire des nœuds du graphe.

Chaque parcours définit l’ordre de parcours des nœuds.

Le parcours en profondeur d’abord d’un graphe consiste à explorer le graphe à partir d’un sommet donné, puis à explorer ses voisins de façon récursive.
Le nom anglais est DFS pour depth-first search.

L’un des buts principaux du parcours en profondeur d’abord est de trouver tous les nœuds accessibles depuis un sommet du graphe.

b. Programmation

Pour implémenter en Python le parcours en largeur d’abord d’un graphe, on peut utiliser la fonction :

parcours_profondeur_rec(graphe, sommet, visite).

Cette fonction prend en paramètres :

graphe un graphe implémenté avec une liste d’adjacence ;
sommet un sommet à partir duquel on réalise le parcours en profondeur ;
visite un tableau des nœuds déjà visités.

Cette fonction renvoie la liste du parcours en profondeur d’abord du graphe à partir du sommet.

Rappel
La liste d’adjacence a une structure de dictionnaire qui a pour clés les sommets et pour valeurs associées aux clés les listes des sommets adjacents.

Voici ci-dessous l’implémentation de cette fonction.

Python	Explication
def parcours_profondeur_rec(graphe, sommet, visite = None):	On définit la fonction. Le tableau visite est initialisé comme étant None.
if visite is None: visite = []	Si visite vaut None, on affecte un tableau vide à visite.
if sommet not in visite: visite.append(sommet)	Si le sommet n’est pas visité, on l’ajoute au tableau visite.
non_visite = [s for s in graphe[sommet] if s not in visite]	On crée un tableau non_visite des nœuds adjacents au sommet qui n’ont pas encore été visités.
for s in non_visite: parcours_profondeur_rec (graphe, s, visite)	À partir de chaque nœud s non visité, on fait un parcours en profondeur
return visite	On retourne le tableau visite.

Exemple
On considère le graphe suivant.

On implémente ce graphe avec une liste d’adjacence :
graphe = {'A' : ['B', 'C'], 'B' : ['A', 'C'], 'C' : ['A', 'B', 'D'], 'D' : ['C'], ‘E’ : []}

Voici l’exécution sur Python Tutor de la fonction parcours_profondeur_rec(graphe, ‘C’).

Le parcours en profondeur de ce graphe d’abord à partir du sommet ‘C’ est donc [‘C’, ‘A’, ‘B’, ‘D’].

2. Le parcours en largeur d’abord

a. Principe

Le parcours en largeur d’abord d’un graphe consiste à explorer le graphe à partir d’un sommet donné, puis à énumérer les nœuds du graphe par distance croissante au sommet initial.
Le nom anglais est BFS pour breadth-first search.

L’un des buts principaux du parcours en largeur d’abord est de trouver tous les nœuds accessibles depuis un sommet en les ordonnant, du plus proche au plus éloigné.

Exemple
On considère le graphe suivant.

Le parcours en largeur de ce graphe à partir du sommet ‘D’ donne :

Distance 0 : ‘D’ ;
Distance 1 : ‘C’ est le seul nœud
à une distance de 1 arête de ‘D’ ;
Distance 2 : ‘A’ et ‘B’ sont les nœuds
à une distance de 2 arêtes de ‘D’ ;
Distance 3 : ‘E’ est le seul nœud
à une distance de 3 arêtes de ‘D’ ;
Distance 4 : ‘F’ est le seul nœud
à une distance de 4 arêtes de ‘D’.

Le parcours en largeur donne donc :

‘D’ — ‘C’ — ‘A’ — ‘B’ — ‘E’ — ‘F’ ou ‘D’ — ‘C’ — ‘B’ — ‘A’ — ‘E’ — ‘F’

En effet, les nœuds à la distance 2 ne sont pas ordonnés. Leur ordre d’apparition dans le parcours en largeur d’abord dépend de la manière dont la liste d’adjacence du graphe est construite.

b. Programmation

Pour implémenter le parcours en largeur d’abord, on utilise la structure linéaire de file qui permet de garder un ordre dans le traitement des données.

Rappel
Dans une file, on enfile et défile des données : les premiers éléments ajoutés à une file seront les premiers à être récupérés.

Pour implémenter la file en Python, on utilise un objet de type list avec la méthode append pour enfiler (ajouter un élément à la file) et l’instruction file.pop(0) pour défiler (retirer le premier élément de la file).

En Python, on utilise la fonction :

parcours_largeur(graphe, sommet).

Cette fonction prend en paramètres :

graphe un graphe implémenté avec une liste d’adjacence ;
sommet un sommet à partir duquel on réalise le parcours en profondeur.

Cette fonction renvoie la liste du parcours en largeur d’abord du graphe à partir du sommet.

Voici ci-dessous l’implémentation de cette fonction.

Python	Explication
def parcours_largeur(graphe, sommet):	On définit la fonction.
visite = [] file = [] file.append(sommet)	On initialise la liste des nœuds visités visite à []. On initialise la file utilisée file à [sommet].
while file: s = file.pop(0)	Tant que file n’est pas vide, on défile file. Le nœud récupéré est s.
if s not in visite: visite.append(s)	Si s n’a pas été visité, alors on l’ajoute au tableau visite.
non_visite = [n for n in graphe[s] if n not in visite]	On crée un tableau non_visite des nœuds adjacents au nœud s qui n’ont pas encore été visités.
file.extend(non_visite)	On enfile dans file tous les éléments du tableau non_visite.
return visite	On retourne le tableau visite.

Remarque
Dans cette fonction, la file est successivement défilée (retrait d’un élément), remplie, défilée, remplie, etc. On sort de la boucle while lorsque la file est vide.

Exemple
On considère le graphe suivant.

On implémente ce graphe avec une liste d’adjacence :

graphe = {'A' : ['B', 'C'], 'B' : ['A', 'C', 'E'], 'C' : ['A', 'B', 'D'], 'D' : ['C'], 'E' : ['B', 'F'], 'F' : ['E']}

Voici l’exécution sur Python Tutor de la fonction parcours_profondeur_rec(graphe, ‘D’).

Le parcours en largeur de ce graphe à partir du sommet ‘D’ est donc [‘D’, ‘C’, ‘A’, ‘B’, ‘E’, ‘F’].

3. La recherche des chemins

a. Principe

On peut adapter le code de la fonction précédente pour que la file stocke au fur et à mesure le tuple (nœud, chemin). Ainsi, en précisant le nœud de départ et le nœud d’arrivée, on peut récupérer tous les chemins qui relient ces deux nœuds.

Exemple
On considère le graphe orienté suivant (attention : les arcs sont orientés).

Deux chemins relient les sommets ‘A’ et ‘F’ :

‘A’ — ‘B’ — ‘F’
‘A’ — ‘C’ — ‘D’ — ‘F’

b. Programmation

Pour implémenter en Python la recherche des chemins dans un graphe, on utilise la fonction :

recherche_chemin(graphe, nœud_init, nœud_fin).

Cette fonction prend en paramètres :

graphe un graphe implémenté avec une liste d’adjacence ;
nœud_init et nœud_fin deux sommets.

Cette fonction renvoie la liste des chemins du graphe de nœud_init à nœud_fin.

Voici ci-dessous l’implémentation de cette fonction.

Python	Explication
def recherche_chemin(graphe, nœud_init, nœud_fin):	On définit la fonction.
file = [] file.append((nœud_init, [nœud_init])) chemins = []	On initialise la file utilisée file à [(nœud_init, [nœud_init])]. On initialise la liste des chemins à [].
while file: sommet, chemin = file.pop(0)	Tant que file n’est pas vide, on défile file. On récupère sommet un nœud et un tableau chemin. (Chemin est le chemin en cours de traitement.)
for s in graphe[sommet]: if s not in chemin:	Pour chaque voisin s de sommet qui n’est pas dans chemin,
if s == nœud_fin: chemins.append(chemin + [s])	si s est le nœud final nœud_fin, alors on a ajoute le chemin chemin+[s] au tableau chemins. (Chemins est la liste de tous les chemins possibles que l'on rajoute au fur et à mesure.)
else: file.append((s, chemin + [s]))	sinon, on ajoute à file le tuple (s,chemin+[s]).
return chemins	On retourne le tableau chemins.

Exemple
On considère le graphe suivant.

On implémente ce graphe avec une liste d’adjacence :
graphe = {'A' : ['B', 'C'], 'B' : ['E', 'F'], 'C': ['D'], 'D' : ['F'], 'E' : [], 'F' : ['C', 'E']}