Retour

Parcours d’un graphe en profondeur d'abord : (Pseudo-code)

Principe

Si le sommet n'est pas déjà visités: on ajoute le sommet au trajet.

Pour chaque voisin du sommet: Si le voisin n'est pas déjà dans le trajet : on relance un nouveau parcours à partir de ce sommet.

On retourne le trajet.

Pour tester cet algorithme, il est plus simple de d'impléter un graphe exemple sous la forme d'une liste des voisins.

Pseudo-codePython

Text Only

VARIABLES
graph: un graphe (liste des voisins)
depart : noeud
voisin : noeud

DEBUT
dfs(graph, depart, visites = None) :
        SI visites est None :
                visites ← liste vide
        FIN SI

        Ajouter depart à visites

        POUR chaque voisin de depart :
                SI voisin n est pas visité :
                        dfs(graph, voisin, visites)
                FIN SI
        FIN POUR

Renvoyer visites
FIN

🐍 Script Python

def pfs(graph, depart, visited=None):
    if visited==None:
        visited = []

    visited.append(depart)

    for v in graph[depart]:
        if v not in visited:
            pfs(graph, v, visited)

    return visited

ma_liste = {'A': ['B', 'C'],
            'B': ['A', 'D', 'E'],
            'C': ['A', 'D'],
            'D': ['B', 'C', 'E'],
            'E': ['B', 'D', 'F', 'G'],
            'F': ['E', 'G'],
            'G': ['E', 'F', 'H'],
            'H': ['G']}

print(pfs(ma_liste, 'E'))
print(bfs(ma_liste, 'E'))