Algorithme

Parcours de graphe

Le parcours de graphe visite tous les sommets accessibles par BFS ou DFS : la base des plus courts chemins non pondérés, composantes, cycles et tri topologique.

Commencer le guide Discussions

Le parcours de graphe consiste à visiter, une seule fois chacun, tous les sommets accessibles depuis un sommet de départ en suivant les arêtes. Les deux stratégies fondamentales sont le parcours en largeur (BFS), qui utilise une file pour progresser couche par couche, et le parcours en profondeur (DFS), qui utilise une pile ou la récursivité pour suivre une branche jusqu'au bout avant de revenir en arrière. On stocke généralement un graphe sous forme de listes d'adjacence ou de matrice d'adjacence, et une grille 2D comme un labyrinthe devient un graphe dès que chaque case est vue comme un sommet.

Les réseaux routiers, les réseaux sociaux, les dépendances entre tâches et les liens web sont des graphes. Le BFS trouve les plus courts chemins lorsque toutes les arêtes ont le même coût, tandis que le DFS sert de base aux composantes connexes, à la détection de cycles et au tri topologique. Les outils de build qui ordonnent leurs tâches, les ramasse-miettes qui déterminent ce qui reste accessible et l'outil de remplissage d'un éditeur d'images reposent tous sur un parcours, et c'est l'un des sujets les plus fréquents en entretien technique.

Commencez par dessiner un petit graphe et suivre à la main l'évolution de la file du BFS et de la pile d'appels du DFS. Implémentez ensuite les deux vous-même, en faisant attention au moment où les sommets sont marqués comme visités et à la façon d'enregistrer distances et parents. Passez enfin aux plus courts chemins dans une grille, au comptage des composantes connexes et au tri topologique avec l'algorithme de Kahn.

Points forts

Représentation des graphes

Les listes d'adjacence occupent O(V + E) et conviennent aux graphes creux ; la matrice teste une arête en O(1) mais occupe O(V^2).

Parcours en largeur (BFS)

Une file visite d'abord les sommets les plus proches : dans un graphe non pondéré, la première distance trouvée est la plus courte.

Parcours en profondeur (DFS)

La récursivité ou une pile descend en profondeur puis remonte ; c'est la base des composantes, des cycles et du backtracking.

Tri topologique

Dans un graphe orienté acyclique, l'algorithme de Kahn ou l'ordre de fin du DFS inversé donne un ordre qui respecte les dépendances.

Domaines d'utilisation

Déplacements minimaux dans les labyrinthes et cartes en grille
Ordre des dépendances dans les systèmes de build et gestionnaires de paquets
Groupes connectés et degrés de séparation dans les réseaux sociaux
Marquage des objets accessibles par le ramasse-miettes

Implémentation de référence

BFS et DFS côte à côte

Le programme construit un graphe non orienté de six sommets sous forme de listes d'adjacence dans un dictionnaire, puis affiche le plus petit nombre d'arêtes de A vers chaque sommet grâce à un BFS fondé sur deque, et l'ordre de visite d'un DFS récursif. Les deux fonctions mémorisent les sommets visités pour n'en traiter aucun deux fois.

graph_traversal.py

from collections import deque

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


def bfs(start):
    """Shortest number of edges from start to every reachable vertex."""
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nxt in graph[node]:
            if nxt not in dist:
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    return dist


def dfs(start):
    """Vertices in depth-first visiting order."""
    order, seen = [], set()

    def visit(node):
        seen.add(node)
        order.append(node)
        for nxt in graph[node]:
            if nxt not in seen:
                visit(nxt)

    visit(start)
    return order


print(bfs("A"))  # {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 3}
print(dfs("A"))  # ['A', 'B', 'D', 'C', 'E', 'F']

python graph_traversal.py

Guide pas à pas

Six chapitres pour aller de l'installation aux notions essentielles de Parcours de graphe.

Documentation officielle et ressources

Discussions

Lancer une discussion

Posez vos questions, partagez votre expérience et échangez vos avis sur Parcours de graphe.

Aucune discussion pour l'instant. Lancez la première.

0 commentaire