Parcourir un graphe en largeur et en profondeur

Parcourir un graphe, c'est visiter tous les sommets que l'on peut atteindre depuis un sommet de départ, chacun une seule fois. On marque les sommets déjà visités : sans ce marquage, un cycle ferait tourner le parcours sans fin.

On représente le graphe par un dictionnaire qui associe à chaque sommet la liste de ses voisins, ici dans l'ordre alphabétique.

Parcours en largeur. On visite le départ, puis tous ses voisins, puis les voisins de ces voisins, et ainsi de suite. On utilise une file : le premier sommet entré est le premier traité.

g = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}

def largeur(g, depart):
    vus = [depart]
    file = [depart]
    while len(file) > 0:
        s = file.pop(0)
        for v in g[s]:
            if v not in vus:
                vus.append(v)
                file.append(v)
    return vus

print(largeur(g, "A"))

['A', 'B', 'C', 'D', 'E', 'F']

Parcours en profondeur. Depuis un sommet, on part vers son premier voisin non visité, et on s'enfonce le plus loin possible ; quand un sommet n'a plus de voisin non visité, on revient en arrière. La version récursive utilise la pile des appels (même graphe g) :

def profondeur(g, s, vus):
    vus.append(s)
    for v in g[s]:
        if v not in vus:
            profondeur(g, v, vus)
    return vus

print(profondeur(g, "A", []))

['A', 'B', 'D', 'E', 'F', 'C']

De A, on va en B, puis en D ; D n'a pas d'autre voisin, on revient en B, on va en E, puis en F ; de F, on atteint enfin C.

On peut aussi l'écrire avec une pile explicite (on empile les voisins à l'envers pour les dépiler dans l'ordre alphabétique) :

def profondeur_pile(g, depart):
    vus = []
    pile = [depart]
    while len(pile) > 0:
        s = pile.pop()
        if s not in vus:
            vus.append(s)
            for v in reversed(g[s]):
                if v not in vus:
                    pile.append(v)
    return vus

print(profondeur_pile(g, "A"))

['A', 'B', 'D', 'E', 'F', 'C']

Plus court chemin en nombre d'arêtes. Le parcours en largeur atteint chaque sommet par un chemin ayant le moins d'arêtes possible. En notant la distance de chaque sommet découvert :

def distances(g, depart):
    d = {depart: 0}
    file = [depart]
    while len(file) > 0:
        s = file.pop(0)
        for v in g[s]:
            if v not in d:
                d[v] = d[s] + 1
                file.append(v)
    return d

print(distances(g, "A"))

{'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 2}

Les parcours servent aussi à chercher un chemin entre deux sommets (le second est-il visité ?) ou à repérer un cycle (atteindre un sommet déjà visité autrement que par l'arête d'où l'on vient). Exemples : sortir d'un labyrinthe, router des paquets dans un réseau.

Énoncé. Un graphe non orienté est donné par ses listes de voisins (ordre alphabétique). Dans quel ordre ses sommets sont-ils visités depuis B, en largeur, puis en profondeur ?

En largeur (file). On visite B et on enfile C et E. On traite C : A est nouveau (E est déjà vu). On traite E : rien de nouveau. On traite A : D est nouveau. Ordre : B, C, E, A, D.

En profondeur (récursif). De B, premier voisin C ; de C, premier voisin non visité A ; de A, D. D est sans issue, on revient en A, puis en C : il reste E. Ordre : B, C, A, D, E.

h = {
    "A": ["C", "D"],
    "B": ["C", "E"],
    "C": ["A", "B", "E"],
    "D": ["A"],
    "E": ["B", "C"],
}

def largeur(g, depart):
    vus = [depart]
    file = [depart]
    while len(file) > 0:
        s = file.pop(0)
        for v in g[s]:
            if v not in vus:
                vus.append(v)
                file.append(v)
    return vus

def profondeur(g, s, vus):
    vus.append(s)
    for v in g[s]:
        if v not in vus:
            profondeur(g, v, vus)
    return vus

print(largeur(h, "B"))
print(profondeur(h, "B", []))

['B', 'C', 'E', 'A', 'D']
['B', 'C', 'A', 'D', 'E']

Graphe g de la leçon (arêtes A–B, A–C, B–D, B–E, C–F, E–F) :