Retour

Parcours d’un graphe en largeur d'abord

Principe

On choisit un sommet de départ SI le sommet est déjà visité, on ne fait rien SINON, on le marque comme visité (en l'ajoutant dans la liste visites) ET Pour chaque sommet connecté, on réitère récursivement cet algorithme

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

Pseudo-codeImplémentation en Python

Text Only

VARIABLES
depart : noeud (origine)
graph : un graphe (liste des voisins)
noeud : noeud
voisin : noeud
file : file (liste vide au départ)
visites : liste
nonvisites : liste

DEBUT
bfs(graph, depart) :
visites ← liste vide
chemin  ← liste vide
enfiler depart dans chemin

TANT QUE chemin n'est pas vide :
noeud ← defiler(chemin)

SI noeud n'appartient pas à visites :
        ajouter noeud à visites
        nonvisites ← listes des voisins de noeud non visités

        POUR chaque s dans nonvisites :
                ajouter s dans chemin à la 1ère position 
        FIN POUR
FIN SI
FIN TANT QUE

Renvoyer visites
FIN

🐍 Script Python

    def bfs(graph, depart):
        visited = []
        file=[]
        file.append(depart)

        while file:
            node = file.pop()

            if node not in visited:
                visited.append(node)
                unvisited = [n for n in graph[node] if n not in visited]

                for s in unvisited:
                    file.insert(0, s)

        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(bfs(ma_liste, 'E'))