C12.4 : Parcours d'un graphe en profondeur

Parcours d'un graphe

Présentation

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.

Parcours d'un graphe en profondeur d'abord

L'objectif est ici d'écrire une fonction qui prend un graphe et un sommet de départ en paramètres et renvoie la liste de tous les sommets du graphe.

Fonction recursive

Quelque soit la méthode utilisée, le parcours d'un graphe nécessite d'identifier les nœuds visités au fur et à mesure du parcours du graphe, c'est pourquoi nous ajouterons une liste des sommets déjà visités en paramètre (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.

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 le IV, nous verrons un algorithme qui permet de connaitre le plus court chemin entre deux nœuds.

Recherche d'un cycle dans un graphe

Cycle dans un graphe

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 True

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

3) Pourquoi est-il nécessaire d'appliquer la recherche en commençant par tous les sommets ?

4) Tester le programme.