Parcours en largeur (BFS)

Le BFS (Breadth-First Search) explore un graphe niveau par niveau, comme une onde qui se propage depuis un caillou jete dans l'eau. D'abord les voisins directs, puis les voisins des voisins, etc.

Pour implémenter le BFS, on utilise une file (premier entre, premier sorti). En Python, c'est collections.deque avec popleft() pour retirer le premier élément et append() pour en ajouter un.

On a aussi besoin d'un ensemble de noeuds deja vus pour eviter de tourner en rond dans les cycles.

Le graphe est représente par un dictionnaire de listes d'adjacence :

graphe = {'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A'], 'D': ['B']}
bfs(graphe, 'A') donne ['A', 'B', 'C', 'D']

Écris une fonction bfs(graphe, depart) qui retourne la liste des noeuds visites dans l'ordre du BFS.

Tests (2/4)

BFS simple

g = {'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A'], 'D': ['B']}
résultat = bfs(g, 'A')
assert résultat[0] == 'A'
assert set(résultat) == {'A', 'B', 'C', 'D'}

Tous visites

g = {'A': ['B'], 'B': ['A', 'C'], 'C': ['B']}
assert len(bfs(g, 'A')) == 3

+ 0 tests cachés

Indices (3 disponibles)

Solution officielle

from collections import deque

def bfs(graphe, depart):
    visites = []
    vus = set()
    file = deque([depart])
    vus.add(depart)
    while file:
        noeud = file.popleft()
        visites.append(noeud)
        for voisin in graphe.get(noeud, []):
            if voisin not in vus:
                vus.add(voisin)
                file.append(voisin)
    return visites

← Representation par liste d'adjacence Parcours en profondeur (DFS) →

solution.py

Bravo!

Parcours en largeur (BFS)

Tests (2/4)

Indices (3 disponibles)

Solution officielle