Parcours de graphe

Le parcours de graphe consiste à visiter systématiquement les sommets et les arêtes d'un graphe ; la recherche en largeur d'abord (BFS) explore niveau par niveau tandis que la recherche en profondeur d'abord (DFS) explore aussi profondément que possible avant de revenir en arrière, et ensemble, elles constituent la base de la plupart des algorithmes de graphe.

Definition

Le parcours de graphe est le processus de visite de chaque sommet (et d'examen de chaque arête) d'un graphe dans un ordre systématique ; la recherche en largeur d'abord visite les sommets par ordre de distance à partir d'une source, et la recherche en profondeur d'abord suit chaque chemin jusqu'à son extrémité avant de revenir en arrière.

Scope

Ce sujet aborde les deux stratégies fondamentales de recherche dans les graphes, la recherche en largeur d'abord (BFS) et la recherche en profondeur d'abord (DFS), leurs implémentations basées sur des files d'attente et des piles, ainsi que les informations structurelles qu'elles révèlent — l'accessibilité, les composantes connexes, les chemins les plus courts dans les graphes non pondérés, l'ordre topologique, la détection de cycles et les composantes fortement connexes. Il exclut les chemins les plus courts pondérés et les problèmes de flux, qui s'appuient sur le parcours mais sont traités séparément.

Core questions

• En quoi la BFS et la DFS diffèrent-elles dans l'ordre de visite des sommets, et que révèle chacune d'elles ?
• Comment la BFS calcule-t-elle les chemins les plus courts dans un graphe non pondéré ?
• Comment la DFS permet-elle le tri topologique, la détection de cycles et la décomposition en composantes ?
• Pourquoi les deux parcours s'exécutent-ils en temps linéaire par rapport au nombre de sommets plus les arêtes ?
• Comment les marqueurs de visite et les structures de frontière sont-ils utilisés pour éviter de revisiter les sommets ?

Key concepts

• recherche en largeur d'abord (BFS)
• recherche en profondeur d'abord (DFS)
• ensemble des sommets visités
• frontières basées sur des files d'attente et des piles
• composantes connexes
• tri topologique
• détection de cycles
• composantes fortement connexes

Key theories

Recherche en largeur d'abord et chemins les plus courts non pondérés

La BFS visite les sommets par ordre non décroissant de distance par rapport à la source en utilisant une file d'attente, ce qui lui permet de calculer le nombre minimal d'arêtes de la source à chaque sommet accessible en temps linéaire.

Recherche en profondeur d'abord et algorithmes de graphe linéaires

La DFS, avec ses temps de découverte et de fin et sa classification des arêtes, permet des algorithmes en temps linéaire pour le tri topologique, la détection de cycles et la recherche de composantes fortement connexes, tels que systématisés par Tarjan.

Clinical relevance

Les algorithmes de parcours sont omniprésents : la BFS trouve les nombres de sauts les plus courts dans les réseaux non pondérés et est à la base des robots d'exploration web et de la diffusion pair-à-pair ; la DFS est utilisée pour la résolution de dépendances et les systèmes de construction via le tri topologique, la détection d'interblocages, la résolution de labyrinthes et d'énigmes, et l'analyse de composantes dans les réseaux sociaux et biologiques.

History

La recherche en largeur d'abord remonte aux travaux de Moore en 1959 sur le routage de labyrinthes et à des efforts indépendants connexes. La recherche en profondeur d'abord a été établie sur des bases algorithmiques rigoureuses par Robert Tarjan en 1972, dont les algorithmes en temps linéaire pour les composantes fortement connexes et la biconnexité ont démontré que la DFS est un outil général puissant.

Key figures

• Robert Tarjan
• Edward F. Moore
• John Hopcroft

Seminal works

• tarjan1972
• cormen2009

Frequently asked questions

Quand devrais-je utiliser la BFS plutôt que la DFS ?

Utilisez la BFS lorsque vous avez besoin du chemin le plus court en termes de nombre d'arêtes ou que vous souhaitez explorer le graphe par ordre de distance à partir d'une source. Utilisez la DFS pour les problèmes de structure — ordre topologique, détection de cycles, composantes connexes ou fortement connexes — où l'exploration en profondeur et le retour en arrière sont naturels.

Pourquoi la BFS et la DFS sont-elles toutes deux en temps linéaire ?

Chaque sommet est marqué comme visité et traité une seule fois, et chaque arête est examinée un nombre constant de fois, de sorte que le travail total est proportionnel au nombre de sommets plus le nombre d'arêtes, noté O(V + E).