C12.4 : Parcours d'un graphe en profondeur
Parcours d'un graphe
Présentation
Parcourir un graphe à partir d'un sommet (nœud), consiste à visiter tous les sommets possibles à partir de ce sommet.
Application
Considérons le graphe suivant.
Proposer une méthode systématisée pour parcourir tous les nœuds à partir du nœud de valeur 0. La méthode proposée doit pouvoir être appliquée à un graphe très grand en étant sûr de n'oublier aucun nœud.
Principe à suivre
Pour parcourir un graphe, il est nécessaire de "marquer" les sommets déjà visités pour ne pas les parcourir à nouveau.
Parcours d'un graphe en profondeur d'abord
Principe général du parcours en profondeur d'un graphe
Le principe général, récursif, du parcours d'un graphe en profondeur est le suivant :
Fonction recursive
Ici, le "marquage" des sommets visités se fera à l'aide d'une liste passée en paramètre de la fonction (liste qui sera vide au premier appel de la fonction).
Voici la fonction qui permet cela (elle nécessite l'utilisation de la classe précédente).
Vous noterez, entre autres, que cette fonction ne renvoie rien, mais qu'elle a un effet de bord sur le paramètre liste_sommets_visites.
def parcours_rec_profondeur(g, noeud, liste_sommets_visites):
liste_sommets_visites.append(noeud)
for voisin in g.liste_voisins(noeud):
if voisin not in liste_sommets_visites:
parcours_rec_profondeur(g, voisin, liste_sommets_visites)1) Sans utiliser l'ordinateur, expliciter le déroulement pas à pas du programme lorsqu'on applique cette fonction aux deux graphes ci-dessous en partant du nœud ①.
2) Quelle est la particularité du résultat pour le graphe C2 ?
3) Écrire le code du programme principal qui permet de vérifier le bon fonctionnement de cette fonction avec les deux graphes ci-dessus.
Encapsulation de la fonctions récursive
Écrire une fonction qui prend un graphe et un sommet en paramètres et renvoie la liste des nœuds connexes au sommet choisi (c'est-à-dire ceux pour lesquels il existe un chemin). On utilisera sans la modifier la fonction du II.1.
Application : Existence d'un chemin entre deux nœuds
Écrire une fonction qui prend un graphe et deux nœuds en paramètres et renvoie True s'il existe un chemin entre les deux et False dans le cas contraire. On utilisera sans la modifier la fonction du II.1.
Remarque n° 1 : dans l'exercice 1, nous verrons comment renvoyer un chemin entre les deux nœuds.
Remarque n° 2 : dans l'exercice 3, nous verrons un algorithme qui permet de connaitre le plus court chemin entre deux nœuds.
Application : Recherche d'un cycle dans un graphe
Cycle dans un graphe
Définition : Un cycle est un chemin dont les extrémités sont identiques.
A faire) Proposer :
- - un graphe non-orienté et un graphe orienté qui présentent un cycle ;
- - un graphe non-orienté et un graphe orienté qui n'en présentent pas.
Détermination de la présence d'un cycle
La détermination de la présence d'un cycle peut se faire à l'aide d'un parcours en profondeur.
Un graphe présente un cycle si l'un des parcours à partir de l'un des sommets retombe sur un nœuds du chemin qui est en train d'être parcouru.
Lors des parcours, il faut donc distinguer trois types de nœuds auxquels ont attribuera arbitrairement les couleurs blanc gris et noir :
- - nœuds blancs : nœuds qui n'ont jamais été vus ;
- - nœuds gris : nœuds des chemins dont le parcours n'est pas terminé ;
- - nœuds noir : nœuds des chemins qui ont fini d'être parcourus.
Si, lors du parcours, le programme rencontre un nœuds gris, c'est que la graphe présente un cycle.
Pour programmer cela, on va utiliser un dictionnaire dont les clés sont les nœuds et les valeurs leur couleur.
Voici le programme. Il nécessite l'utilisation de la classe Graph. Il est constitué de deux fonctions, l'une d'initialisation/lancement, l'autre recursive.
def parcours_rec_cycle(g, s, dico_types):
if dico_types[s] == "gris":
return True
if dico_types[s] == "noir":
return False
dico_types[s] = "gris"
for voisin in g.liste_voisins(s):
if parcours_rec_cycle(g, voisin, dico_types):
return True
dico_types[s] = "noir"
return False
def test_cycle(g):
dico = {}
for sommet in g.liste_sommets():
dico[sommet] = "blanc"
for sommet in g.liste_sommets():
if parcours_rec_cycle(g, sommet, dico):
return True1) Sans utiliser l'ordinateur, représenter, en couleur, le graphe D1 à chaque étape de l'exécution de la fonction parcours_rec_cycle en partant du sommet 1.
2) Sans utiliser l'ordinateur, représenter, en couleur, le graphe D2 à chaque étape de l'exécution de la fonction parcours_rec_cycle en partant du sommet 1.
3) Pourquoi est-il nécessaire d'appliquer la recherche en commençant par tous les sommets ?
4) Tester le programme.