Breadth-First Search (BFS)
Level-by-level graph traversal guaranteeing shortest paths in unweighted graphs. BFS uses a queue to explore vertices level by level, making it optimal for finding shortest paths and solving problems that require exploring nearest neighbors first.
Visualization
Interactive visualization for Breadth-First Search (BFS)
Interactive visualization with step-by-step execution
Implementation
1function bfs(graph: Map<number, number[]>, start: number): number[] {
2 const visited = new Set<number>();
3 const queue = [start];
4 const result: number[] = [];
5
6 visited.add(start);
7
8 while (queue.length > 0) {
9 const node = queue.shift()!;
10 result.push(node);
11
12 const neighbors = graph.get(node) || [];
13 for (const neighbor of neighbors) {
14 if (!visited.has(neighbor)) {
15 visited.add(neighbor);
16 queue.push(neighbor);
17 }
18 }
19 }
20
21 return result;
22}Deep Dive
Theoretical Foundation
Breadth-First Search (BFS) is a fundamental graph traversal algorithm that explores vertices level by level. Starting from a source vertex, BFS visits all its adjacent neighbors first, then visits all neighbors of those neighbors, and so on. It uses a queue data structure (FIFO - First In First Out) to maintain the order of exploration. BFS guarantees finding the shortest path in unweighted graphs. The algorithm is the foundation for many advanced graph algorithms including Dijkstra's shortest path, Prim's minimum spanning tree, and Kahn's algorithm for topological sorting. BFS maintains a visited array to avoid revisiting vertices and infinite loops in cyclic graphs.
Complexity
Time
O(V + E)
O(V + E)
O(V + E)
Space
O(V)
Applications
Industry Use
Finding shortest path in unweighted graphs (GPS navigation)
Social network analysis (friend recommendations, degrees of separation)
Web crawling and indexing (search engines)
Network broadcasting and routing protocols
Shortest path in maze/puzzle solving
Level-order traversal of binary trees
Finding connected components in networks
Cycle detection in graphs
Topological sorting (Kahn's algorithm)
Peer-to-peer networks and file sharing
Use Cases
Related Algorithms
Depth-First Search (DFS)
Graph traversal exploring as deep as possible before backtracking. DFS is a fundamental algorithm that uses a stack (either implicitly through recursion or explicitly) to explore graph vertices. It's essential for cycle detection, topological sorting, and pathfinding problems.
Dijkstra's Algorithm
Finds shortest path from source to all vertices in weighted graph with non-negative edges. Uses greedy approach with priority queue.
Floyd-Warshall Algorithm
Floyd-Warshall is an all-pairs shortest path algorithm that finds shortest distances between every pair of vertices in a weighted graph. Unlike Dijkstra (single-source), it computes shortest paths from all vertices to all other vertices simultaneously. The algorithm can handle negative edge weights but not negative cycles. Developed independently by Robert Floyd, Bernard Roy, and Stephen Warshall in the early 1960s.
Kruskal's Algorithm
Minimum Spanning Tree algorithm using greedy approach and Union-Find data structure. Sorts edges by weight and selects minimum weight edges that don't create cycles. Named after Joseph Kruskal, it's one of the most efficient MST algorithms for sparse graphs.