Se déplacer dans un graphe

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

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

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.

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

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’].

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.

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).

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.

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’].

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’

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.

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']}

Voici l’exécution sur Python Tutor de la fonction recherche_chemin(graphe, 'A', 'F').

Les chemins du graphe entre le sommet ‘A’ et le sommet ‘F’ sont donc ['A', 'B', 'F'] et ['A', 'C', 'D', 'F'].