Parcours en largeur (BFS)
Dernière mise à jour
Le parcours en largeur explore un graphe niveau par niveau. En partant d'un nœud source, il visite d'abord tous ses voisins immédiats, puis tous les voisins non visités de ceux-ci, et ainsi de suite - s'étendant vers l'extérieur en anneaux de distance croissante. Appuyez sur lecture ci-dessus pour le voir se déployer depuis le nœud de départ une couche à la fois.
Le BFS utilise une file de type premier entré, premier sorti, ce qui impose l'ordre niveau par niveau. Comme il atteint les nœuds dans l'ordre de la distance en sauts, le BFS trouve le plus court chemin (le moins d'arêtes) dans un graphe non pondéré. Il visite chaque nœud et chaque arête une fois, donc il s'exécute en temps O(V + E).
Complexité en temps et en espace
| Mesure | Complexité | Remarques |
|---|---|---|
| Temps | O(V + E) | Chaque sommet et arête visité une fois |
| Espace | O(V) | File + ensemble des visités, au pire cas tous les nœuds |
| Parcours | Niveau par niveau | Les nœuds les plus proches d'abord, en anneaux |
| Plus court chemin | Oui (non pondéré) | Atteint chaque nœud avec le moins d'arêtes |
Étape par étape
| Étape | Ce qui se passe |
|---|---|
| 1 | Enfile le nœud source. |
| 2 | Défile le nœud en tête et marque-le comme visité. |
| 3 | Examine chacun de ses voisins. |
| 4 | Enfile tout voisin qui n'est pas déjà visité ou en file. |
| 5 | Répète jusqu'à ce que la file soit vide. |
Exemple résolu
Parcours de ce graphe depuis le nœud 0, où 0-1, 0-2, 1-3, 2-3, 2-4 sont des arêtes :
| Étape | Visités | File (frontière) |
|---|---|---|
| Début | {} | [0] |
Défile 0 | {0} | [1, 2] |
Défile 1 | {0, 1} | [2, 3] |
Défile 2 | {0, 1, 2} | [3, 4] |
Défile 3 | {0, 1, 2, 3} | [4] |
Défile 4 | {0, 1, 2, 3, 4} | [] (terminé) |
Quand utiliser le BFS
| Utilisez-le quand | Évitez-le quand |
|---|---|
| Vous avez besoin du plus court chemin dans un graphe non pondéré | Les arêtes ont des poids - utilisez Dijkstra à la place |
| La cible est probablement proche de la source | Le graphe est très large - la file peut contenir une frontière énorme |
| Vous voulez explorer un graphe dans l'ordre des niveaux | Vous devez seulement atteindre un nœud quelconque, où le DFS utilise moins de mémoire |
| Vous cherchez des composantes connexes ou un trajet à sauts minimaux | Vous avez besoin d'un tri topologique ou d'une détection de cycle - le DFS convient mieux |
Code de Breadth-First Search
Une implémentation propre et exécutable de Breadth-First Search en Python, JavaScript, Java, C++, C. Choisissez un langage, copiez le code ou ouvrez-le préchargé dans le Playground Coddy.
Code de Breadth-First Search en Python
1from collections import deque2
3
4def bfs(graph, start):5 visited = {start}6 queue = deque([start])7 order = []8 while queue:9 node = queue.popleft()10 order.append(node)11 for neighbor in graph[node]:12 if neighbor not in visited:13 visited.add(neighbor) # mark on enqueue, not dequeue14 queue.append(neighbor)15 return order16
17
18graph = {19 "A": ["B", "C"],20 "B": ["D", "E"],21 "C": ["F"],22 "D": [],23 "E": ["F"],24 "F": [],25}26
27print("BFS order:", " -> ".join(bfs(graph, "A")))Code de Breadth-First Search en JavaScript
1const graph = {2 A: ["B", "C"],3 B: ["D", "E"],4 C: ["F"],5 D: [],6 E: ["F"],7 F: [],8};9
10function bfs(start) {11 const visited = new Set([start]);12 const queue = [start];13 const order = [];14 while (queue.length > 0) {15 const node = queue.shift(); // Dequeue the oldest node16 order.push(node);17 for (const next of graph[node]) {18 if (!visited.has(next)) {19 visited.add(next);20 queue.push(next);21 }22 }23 }24 return order;25}26
27console.log("BFS from A:", bfs("A").join(" -> "));Code de Breadth-First Search en Java
1import java.util.ArrayDeque;2import java.util.List;3import java.util.Queue;4
5public class Main {6 public static void main(String[] args) {7 List<List<Integer>> adj = List.of(8 List.of(1, 2), // neighbors of 09 List.of(0, 3, 4), // neighbors of 110 List.of(0, 5),11 List.of(1),12 List.of(1, 5),13 List.of(2, 4)14 );15 boolean[] visited = new boolean[adj.size()];16 Queue<Integer> queue = new ArrayDeque<>();17 visited[0] = true;18 queue.add(0);19
20 StringBuilder order = new StringBuilder("BFS from 0:");21 while (!queue.isEmpty()) {22 int node = queue.poll();23 order.append(" ").append(node);24 // Mark neighbors when enqueued so nothing enters twice25 for (int next : adj.get(node)) {26 if (!visited[next]) {27 visited[next] = true;28 queue.add(next);29 }30 }31 }32 System.out.println(order);33 }34}Code de Breadth-First Search en C++
1#include <iostream>2#include <queue>3#include <vector>4
5void bfs(int start, const std::vector<std::vector<int>>& adj) {6 std::vector<bool> visited(adj.size(), false);7 std::queue<int> frontier;8 visited[start] = true;9 frontier.push(start);10 // Visit nodes level by level11 while (!frontier.empty()) {12 int node = frontier.front();13 frontier.pop();14 std::cout << node << " ";15 for (int next : adj[node]) {16 if (!visited[next]) {17 visited[next] = true;18 frontier.push(next);19 }20 }21 }22}23
24int main() {25 // 6-node undirected graph as an adjacency list26 std::vector<std::vector<int>> adj = {27 {1, 2}, // 028 {0, 3, 4}, // 129 {0, 5}, // 230 {1}, // 331 {1, 5}, // 432 {2, 4}, // 533 };34 std::cout << "BFS from node 0: ";35 bfs(0, adj);36 std::cout << "\n";37 return 0;38}Code de Breadth-First Search en C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 65
6void bfs(int start, const int adj[N][N]) {7 bool visited[N] = {false};8 int queue[N]; // fixed-size queue: head chases tail9 int head = 0, tail = 0;10 visited[start] = true;11 queue[tail++] = start;12 // Visit nodes level by level13 while (head < tail) {14 int node = queue[head++];15 printf("%d ", node);16 for (int next = 0; next < N; next++) {17 if (adj[node][next] && !visited[next]) {18 visited[next] = true;19 queue[tail++] = next;20 }21 }22 }23}24
25int main(void) {26 // 6-node undirected graph as an adjacency matrix27 int adj[N][N] = {28 {0, 1, 1, 0, 0, 0},29 {1, 0, 0, 1, 1, 0},30 {1, 0, 0, 0, 0, 1},31 {0, 1, 0, 0, 0, 0},32 {0, 1, 0, 0, 0, 1},33 {0, 0, 1, 0, 1, 0},34 };35 printf("BFS from node 0: ");36 bfs(0, adj);37 printf("\n");38 return 0;39}FAQ sur le parcours en largeur
Quelle est la complexité temporelle du BFS ?
O(V + E), où V est le nombre de sommets et E le nombre d'arêtes, puisqu'il visite chaque sommet une fois et examine chaque arête une fois. Il utilise O(V) d'espace pour la file et l'ensemble des visités.Le BFS trouve-t-il le plus court chemin ?
Oui, dans un graphe non pondéré. Comme le BFS atteint les nœuds dans l'ordre de la distance en sauts depuis la source, la première fois qu'il atteint un nœud, c'est par un chemin comportant le moins d'arêtes. Pour les graphes pondérés, il vous faut l'algorithme de Dijkstra.
Quelle est la différence entre BFS et DFS ?
Le BFS utilise une file et explore niveau par niveau (les plus proches d'abord), tandis que le DFS utilise une pile et plonge en profondeur le long d'une branche avant de revenir en arrière. Le BFS trouve les plus courts chemins non pondérés ; le DFS utilise moins de mémoire sur les graphes larges et convient à la détection de cycles et au tri topologique.
Quand dois-je utiliser le BFS plutôt que l'algorithme de Dijkstra ?
O(V + E) sans file de priorité. L'algorithme de Dijkstra est nécessaire quand les arêtes portent des poids différents ; exécuter un BFS pur sur un graphe pondéré donne le chemin au moins de sauts, pas celui au moindre coût.Pourquoi le BFS a-t-il besoin d'un ensemble des visités ?
Les graphes peuvent contenir des cycles, donc sans ensemble des visités le BFS enfilerait le même nœud à répétition et bouclerait à l'infini. Marquer un nœud lorsqu'on l'enfile pour la première fois (et non lorsqu'on le défile) empêche aussi le même nœud d'être ajouté deux fois à la file par des voisins différents.
Dois-je marquer un nœud comme visité à l'enfilage ou au défilage ?
Marquez-le à l'enfilage. Si vous attendez de le défiler, un nœud peut être ajouté plusieurs fois à la file par des voisins différents avant d'être traité, gaspillant mémoire et temps. Marquer à l'enfilage garantit que chaque nœud entre dans la file exactement une fois.
Ressources associées
Plus de visualisations
