Parcours de graphes orientés⚓︎

Principe des parcours de graphes

Les graphes peuvent se parcourir en largeur ou en profondeur, comme les arbres. La différence fondamentale entre les deux parcours repose sur la structure utilisée pour stocker les sommets vus au cours de l'exploration du graphe.

Pour un parcours en largeur, on utilise une file. Pour un parcours en profondeur, on utilise une pile. Dans ce dernier cas, on peut également utilisé la récursivité et la pile d'appels pour remplacer la pile de la version itérative.

Voici les versions itérative de ces deux parcours, avec des fonctions génériques sommets et voisins qu'il faut adapter en fonction de l'implémentation choisie.

Parcours en largeur

def parcours_largeur(graphe, depart):
    file_attente = file_vide()
    etat = {s: "pas vu" for s in sommets(graphe)}
    etat[depart] = "vu"
    enfile(depart, file_attente)
    while not est_vide(file_attente):
        s = defile(file_attente)
        for v in voisins(s, graphe):
            if etat[v] == "pas vu":
                enfile(v, file_attente)
                etat[v] = "vu"
        etat[s] = "traité"
    return QUELQUE_CHOSE_OU_PAS

Parcours en profondeur

def parcours_profondeur(graphe, depart):
    pile = pile_vide()
    etat = {s: "pas vu" for s in sommets(graphe)}
    etat[depart] = "vu"
    empile(depart, pile)
    ordre_parcours = []
    while not est_vide(pile):
        s = depile(pile)
        ordre_parcours.append(s)
        for v in voisins(s, graphe):
            if etat[v] == "pas vu":
                empile(v, pile)
                etat[v] = "vu"
        etat[s] = "traité"
    return QUELQUE_CHOSE_OU_PAS

Les 3 états permettent de distinguer les sommets qui n'ont pas été atteints, ceux qui sont en cours de traitement et ceux qui ont fini d'être traités.

Selon les algorithmes, on pourra garder ces 3 états, fusionner les deux derniers ou changer le nom de ces états, éventuellement avec des nombres (0, 1 et 2).

Modélisation des files et des piles

Pour les files et les piles, vous pourrez utiliser dans tous les exercices suivants les fonctions suivantes :

Implémentation des files et des piles

from collections import deque

def file_vide():
    return deque()
def enfiler(val, file):
    file.append(val)
def defiler(file):
    return file.popleft()

def pile_vide():
    return []
def empiler(val, pile):
    pile.append(val)
def depiler(pile):
    return pile.pop()

def est_vide(structure):
    return len(structure) == 0

Les graphes utilisés

Pour les deux exercices, on utilisera le graphe suivant, appelé graphe_exemple:

Il est défini à l'aide de la classe Graphe de la partie précédente.

Les 3 graphes suivants sont également déjà définis :

`graphe1`	`graphe2`	`graphe3`

Exemples de parcours sur le graphe 2

Voici la façon dont sont visités les sommets de graphe2 en partant de 0 avec un parcours en largeur et un parcours en profondeur.

Pour des raisons techniques, il faut séparer les étapes en 2 parties.

Exercice 7 : étude du parcours en largeur

En rajoutant des print dans la fonction parcours_largeur, retrouver les états successifs de la file d'attente pour le graphe graphe_exemple en partant de "A".

Évaluations restantes : ∞/∞

Exercice 8 : étude du parcours en profondeur

En rajoutant des print dans la fonction parcours_profondeur, retrouver les états successifs de la pile d'attente pour le graphe graphe_exemple en partant de "A".

Évaluations restantes : ∞/∞