BFS of graph

Time: O(V+E)

Space: O(V)

Intuition

BFS explores nodes level by level using a queue. Start from source, enqueue all unvisited neighbors, mark them visited when enqueued (not when dequeued) to avoid duplicate processing.

Algorithm

1visited[src]=true. Enqueue src.
2While queue not empty: dequeue u. Add u to result.
3For each neighbor v of u: if not visited: visited[v]=true, enqueue v.

Example Walkthrough

Input: Graph: 0â†’[1,2], 1â†’[3], 2â†’[3], 3â†’[]

1.Queue:[0]. Dequeue 0 â†’ result=[0]. Enqueue 1,2.
2.Dequeue 1 â†’ result=[0,1]. Enqueue 3. Dequeue 2 â†’ result=[0,1,2]. Dequeue 3 â†’ result=[0,1,2,3].

Output: [0,1,2,3]

Common Pitfalls

•Mark visited when ENQUEUING, not when dequeuing â€” prevents the same node being enqueued multiple times.

BFS of graph.java

Java

// Approach: BFS using a queue. Start from source, mark visited, enqueue adjacent unvisited nodes.
// Process level by level until all reachable nodes are visited.
// Time: O(V+E) Space: O(V)
import java.util.*;

class Solution {
    // Function to return Breadth First Search Traversal of given graph.
    public ArrayList<Integer> bfs(ArrayList<ArrayList<Integer>> adj) {
        ArrayList<Integer> traversal = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        int size = adj.size();
        boolean[] visited = new boolean[size];
        queue.add(0);
        visited[0] = true;
        while (!queue.isEmpty()) {
            int pop = queue.poll();
            traversal.add(pop);

            for (int i = 0; i < adj.get(pop).size(); i++) {
                int current = adj.get(pop).get(i);

                if (!traversal.contains(current) && visited[current] != true) {
                    queue.add(current);
                    visited[current] = true;
                }
            }
        }
        return traversal;
    }
}

Was this solution helpful?