Implement BFS algorithm
Problem Statement
Given a graph represented as an adjacency list and a starting vertex, perform a Breadth-First Search (BFS) traversal and return the order in which vertices are visited.
Example:
- Input:
V = 5, Edges = [[0,1],[0,2],[1,3],[2,4]], start = 0 - Output:
[0, 1, 2, 3, 4]
Noob-Friendly Explanation
Imagine you're standing at the entrance of a building and you want to explore every room. BFS means you first visit all the rooms directly connected to where you are before going deeper. It's like ripples in a pond — the wave goes outward level by level.
You use a queue (first-in-first-out line, like a queue at a store). You put the starting room in the queue, then keep taking a room out, visiting it, and adding its unvisited neighbors to the back of the queue.
Approach 1: Brute Force (Using Adjacency Matrix)
Intuition
Store the graph using an adjacency matrix and perform BFS using a queue. For each vertex, scan the entire row to find its neighbors.
Algorithm
- Create a V×V adjacency matrix from the edges.
- Use a queue starting with the source vertex.
- Mark the source as visited.
- While the queue is not empty, dequeue a vertex, print it, and enqueue all unvisited neighbors found by scanning the matrix row.
import java.util.LinkedList;
import java.util.Queue;
public class BFSBruteForce {
public static void bfs(int V, int[][] edges, int start) {
int[][] matrix = new int[V][V];
for (int[] edge : edges) {
matrix[edge[0]][edge[1]] = 1;
matrix[edge[1]][edge[0]] = 1;
}
boolean[] visited = new boolean[V];
Queue<Integer> queue = new LinkedList<>();
visited[start] = true;
queue.add(start);
while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " ");
// Scan entire row to find neighbors — O(V) per vertex
for (int i = 0; i < V; i++) {
if (matrix[node][i] == 1 && !visited[i]) {
visited[i] = true;
queue.add(i);
}
}
}
}
public static void main(String[] args) {
int V = 5;
int[][] edges = {{0,1},{0,2},{1,3},{2,4}};
bfs(V, edges, 0); // Output: 0 1 2 3 4
}
}Complexity Analysis
- Time Complexity: O(V^2) — for each vertex we scan an entire row of size V.
- Space Complexity: O(V^2) — the adjacency matrix takes V×V space.
Approach 2: Optimal (Using Adjacency List)
Intuition
Store the graph using an adjacency list so we only look at actual neighbors instead of scanning all V vertices. Use a queue for BFS traversal.
Algorithm
- Build an adjacency list from the edges.
- Create a visited array and a queue.
- Mark the starting vertex as visited and enqueue it.
- While the queue is not empty, dequeue a vertex, process it, and enqueue all unvisited neighbors.
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class BFSOptimal {
public static List<Integer> bfs(int V, int[][] edges, int start) {
// Build adjacency list
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) {
adj.add(new ArrayList<>());
}
for (int[] edge : edges) {
adj.get(edge[0]).add(edge[1]);
adj.get(edge[1]).add(edge[0]);
}
List<Integer> result = new ArrayList<>();
boolean[] visited = new boolean[V];
Queue<Integer> queue = new LinkedList<>();
visited[start] = true;
queue.add(start);
while (!queue.isEmpty()) {
int node = queue.poll();
result.add(node);
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.add(neighbor);
}
}
}
return result;
}
public static void main(String[] args) {
int V = 5;
int[][] edges = {{0,1},{0,2},{1,3},{2,4}};
List<Integer> result = bfs(V, edges, 0);
System.out.println(result); // [0, 1, 2, 3, 4]
}
}Complexity Analysis
- Time Complexity: O(V + E) — each vertex and edge is processed exactly once.
- Space Complexity: O(V) — for the visited array and queue (adjacency list takes O(V + E) but that's the input).