Step 4 of 6

67% Complete

Breadth-First Search (BFS)

Learn the BFS graph traversal algorithm

What is Breadth-First Search?

Breadth-First Search (BFS) is a graph traversal algorithm that explores vertices level by level. It visits all neighbors of a vertex before moving to their neighbors. BFS uses a queue (FIFO) to maintain the frontier of vertices to visit. It's ideal for finding shortest paths in unweighted graphs.

BFS is always implemented iteratively using an explicit queue, unlike DFS which can be recursive.

How BFS Works

BFS Algorithm Steps

Start at a source vertex and add to queue
Mark it as visited
Remove vertex from queue
Add all unvisited neighbors to queue and mark as visited
Repeat until queue is empty

BFS Traversal - Visual Example

// Graph: 0 - 1 - 3
//         |   |
//         2   4
 
// BFS from vertex 0:
// Queue: [0], Visited: {0}
// Process 0: Add neighbors 1, 2
// Queue: [1, 2], Visited: {0, 1, 2}
// Process 1: Add neighbors 3, 4
// Queue: [2, 3, 4], Visited: {0, 1, 2, 3, 4}
// Process 2: No new neighbors
// Queue: [3, 4], Visited: {0, 1, 2, 3, 4}
// Process 3: No new neighbors
// Queue: [4], Visited: {0, 1, 2, 3, 4}
// Process 4: No new neighbors
// Queue: []
 
// BFS Order: 0 → 1 → 2 → 3 → 4
// Level order: Visit by distance from source

BFS Implementation

BFS - Using Queue

import java.util.*;
 
public class BFS {
    private List<Integer>[] adj;
    private int V;
    
    public BFS(int V) {
        this.V = V;
        adj = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
    }
    
    public void addEdge(int u, int v) {
        adj[u].add(v);
        adj[v].add(u);
    }
    
    // BFS traversal
    public List<Integer> bfs(int start) {
        List<Integer> traversalOrder = new ArrayList<>();
        boolean[] visited = new boolean[V];
        Queue<Integer> queue = new LinkedList<>();
        
        // Start BFS
        queue.add(start);
        visited[start] = true;
        
        while (!queue.isEmpty()) {
            // Remove vertex from queue
            int v = queue.remove();
            traversalOrder.add(v);
            
            // Add unvisited neighbors
            for (int neighbor : adj[v]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
        
        return traversalOrder;
    }
    
    public static void main(String[] args) {
        BFS g = new BFS(5);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 3);
        g.addEdge(1, 4);
        
        List<Integer> result = g.bfs(0);
        System.out.println("BFS traversal: " + result);
        // Output: [0, 1, 2, 3, 4]
    }
}

Shortest Path with BFS

Finding Shortest Path in Unweighted Graph

public class BFSShortestPath {
    private List<Integer>[] adj;
    private int V;
    
    public BFSShortestPath(int V) {
        this.V = V;
        adj = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
    }
    
    public void addEdge(int u, int v) {
        adj[u].add(v);
        adj[v].add(u);
    }
    
    // Find shortest path from source to target
    public List<Integer> shortestPath(int source, int target) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[V];
        int[] parent = new int[V];
        
        // Initialize
        queue.add(source);
        visited[source] = true;
        Arrays.fill(parent, -1);
        
        // BFS to find target
        while (!queue.isEmpty()) {
            int v = queue.remove();
            
            if (v == target) {
                break;  // Found target
            }
            
            for (int neighbor : adj[v]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    parent[neighbor] = v;
                    queue.add(neighbor);
                }
            }
        }
        
        // Reconstruct path
        List<Integer> path = new ArrayList<>();
        int current = target;
        while (current != -1) {
            path.add(0, current);  // Add to front
            current = parent[current];
        }
        
        if (path.get(0) == source) {
            return path;
        }
        return new ArrayList<>();  // No path exists
    }
    
    // Get distances from source to all vertices
    public int[] getDistances(int source) {
        Queue<Integer> queue = new LinkedList<>();
        int[] distance = new int[V];
        boolean[] visited = new boolean[V];
        
        Arrays.fill(distance, -1);
        
        queue.add(source);
        visited[source] = true;
        distance[source] = 0;
        
        while (!queue.isEmpty()) {
            int v = queue.remove();
            
            for (int neighbor : adj[v]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    distance[neighbor] = distance[v] + 1;
                    queue.add(neighbor);
                }
            }
        }
        
        return distance;
    }
    
    public static void main(String[] args) {
        BFSShortestPath g = new BFSShortestPath(6);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 3);
        g.addEdge(2, 3);
        g.addEdge(3, 4);
        g.addEdge(3, 5);
        
        List<Integer> path = g.shortestPath(0, 5);
        System.out.println("Shortest path 0→5: " + path);
        
        int[] distances = g.getDistances(0);
        System.out.println("Distances from 0: " + Arrays.toString(distances));
    }
}

BFS Applications

Shortest Path (Unweighted)

Find shortest path in graphs with equal edge weights

Level Order Traversal

Visit nodes by distance/level from source

Connected Components

Find all vertices reachable from a source

Bipartite Check

Check if graph is bipartite (2-colorable)

Social Network Analysis

Find friends, degrees of separation

BFS Complexity Analysis

Time Complexity

O(V + E)

Visit each vertex once, each edge twice

Space Complexity

O(V)

For visited array and queue

Bipartite Graph Check with BFS

Check if Graph is Bipartite

public class BipartiteCheck {
    private List<Integer>[] adj;
    private int V;
    
    public BipartiteCheck(int V) {
        this.V = V;
        adj = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
    }
    
    public void addEdge(int u, int v) {
        adj[u].add(v);
        adj[v].add(u);
    }
    
    // Check if graph is bipartite (can be 2-colored)
    public boolean isBipartite() {
        int[] color = new int[V];
        Arrays.fill(color, -1);  // -1 = uncolored, 0 = color0, 1 = color1
        
        // Check each connected component
        for (int i = 0; i < V; i++) {
            if (color[i] == -1) {
                if (!bfsColor(i, color)) {
                    return false;
                }
            }
        }
        return true;
    }
    
    private boolean bfsColor(int start, int[] color) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        color[start] = 0;
        
        while (!queue.isEmpty()) {
            int v = queue.remove();
            
            for (int neighbor : adj[v]) {
                if (color[neighbor] == -1) {
                    // Color with opposite color
                    color[neighbor] = 1 - color[v];
                    queue.add(neighbor);
                } else if (color[neighbor] == color[v]) {
                    // Adjacent vertices have same color - not bipartite
                    return false;
                }
            }
        }
        return true;
    }
    
    public static void main(String[] args) {
        BipartiteCheck g = new BipartiteCheck(4);
        g.addEdge(0, 1);
        g.addEdge(1, 2);
        g.addEdge(2, 3);
        g.addEdge(3, 0);  // Even cycle - bipartite
        
        System.out.println("Is bipartite: " + g.isBipartite());  // true
    }
}

BFS vs DFS

Aspect	BFS	DFS
Data Structure	Queue (FIFO)	Stack or Recursion (LIFO)
Traversal Order	Level by level	Deep then backtrack
Time	O(V + E)	O(V + E)
Space	O(V) - queue size	O(V) - recursion depth
Shortest Path	✓ Finds optimal	✗ May not be optimal
Cycle Detection	✓ Can detect	✓ Better for this
Implementation	Always iterative	Can be recursive

Key Takeaways

BFS explores graph level by level using a queue
Guarantees shortest path in unweighted graphs
Time complexity O(V + E) like DFS
Space complexity O(V) for queue and visited array
Always iterative (uses explicit queue)
Better than DFS for shortest path problems
Foundation for more complex algorithms (Dijkstra, Prim's)