Algorithm

Breadth-First Search

graph

Breadth-First Search (BFS) is a fundamental graph traversal algorithm that systematically explores a graph by visiting all neighbors at the current depth level before moving to nodes at the next depth. Starting from a source node, BFS uses a queue data structure to maintain the order of exploration, ensuring that nodes are visited in order of their distance from the source. This level-by-level exploration creates a breadth-first tree that reveals the shortest path (in terms of number of edges) from the source to any reachable node. BFS is essential in numerous applications, including finding shortest paths in unweighted graphs, testing bipartiteness, computing network flow, and solving puzzles like the 15-puzzle or Rubik's cube. Its O(V+E) time complexity makes it efficient for both dense and sparse graphs, though it requires O(V) space to store the queue and visited nodes. Unlike Depth-First Search, BFS guarantees finding the shortest path in unweighted graphs and tends to be more useful for finding nodes close to the starting point.

Time: O(V + E)
Space: O(V)
Best: When the target node is at the first level
Worst: When the target node is at the last level or not present

Visualization

No graph data available

Step 1 of 0

Controls & Input

1x

Implementation

Pseudocode

0 function Breadth-First Search(graph, startNode):
1 // Initialize data structures
2 visited = new Set()
3 queue = [startNode]
4 result = []
5
6 // Main BFS loop
7 while queue is not empty:
8 currentNode = queue.shift()
9
10 if currentNode not in visited:
11 visited.add(currentNode)
12 result.append(currentNode)
13
14 // Add unvisited neighbors to queue
15 for neighbor in currentNode.neighbors:
16 if neighbor not in visited:
17 queue.append(neighbor)
18
19 return result