BFS Traversal of Graph
Problem link: https://www.geeksforgeeks.org/problems/bfs-traversal-of-graph/1
Problem Statement
Given a graph of V vertices represented by an adjacency list, perform Breadth First Search (BFS) starting from vertex 0.
Return the BFS traversal of the graph.
Input
- V: number of vertices
- adj: adjacency list where adj[i] contains neighbors of node i
- Graph is connected
Output
- Return list of nodes in BFS traversal order
Example
Input:
V = 5
adj = [[1,2,3],[0],[0,4],[0],[2]]
Output:
0 1 2 3 4
Explanation
Start from node 0 → visit all its neighbors (1,2,3) → then visit neighbors of 2 → node 4.
Brute Force
Intuition
BFS explores nodes level by level. We use a queue to process nodes in the order they are discovered. Start from node 0, visit all neighbors, then move to next level.
Approach
- Create a visited array
- Initialize queue and push node 0
- Mark node 0 as visited
- While queue is not empty:
- Pop node
- Add to result
- Push all unvisited neighbors into queue
- Return result
Visualization
Step 1 of 5- Initial Graph
Graph structure: 0 connects to 1,2,3. 2 connects to 4.
Loading...
Use arrow keys to navigate
Code (Java)
import java.util.*;
class Solution {
public ArrayList<Integer> bfsOfGraph(int V, ArrayList<ArrayList<Integer>> adj) {
boolean[] visited = new boolean[V];
Queue<Integer> queue = new LinkedList<>();
ArrayList<Integer> result = new ArrayList<>();
queue.offer(0);
visited[0] = true;
while(!queue.isEmpty()) {
int node = queue.poll();
result.add(node);
for(int neighbor : adj.get(node)) {
if(!visited[neighbor]) {
visited[neighbor] = true;
queue.offer(neighbor);
}
}
}
return result;
}
}
Time: O(V + E)Space: O(V)
Complexity Analysis
- Time: Each node and edge visited once → O(V + E)
- Space: Queue + visited array → O(V)
Optimal Solution
Intuition
BFS itself is optimal for traversal. No better approach exists for level-order traversal.
Approach
Same as above BFS approach
Code (Java)
// Same as brute (BFS is optimal)
Time: O(V + E)Space: O(V)
Complexity Analysis
- BFS is already optimal
Quick Revision (Brute Force)
- Use queue for BFS
- Visit level by level
- Mark visited when pushing
Quick Revision (Optimal)
- BFS is optimal
- Avoid revisiting nodes
- Queue drives traversal