Shortest paths in unweighted graphs and grids. Finding friends within k connections in a social network. Web crawlers that explore links level by level. Checking whether a graph is bipartite. Level order traversal of trees.

Breadth First Search (BFS) Algorithm

Q: What is breadth-first search?

Breadth-first search (BFS) explores a graph level by level: first the start vertex, then all its neighbours, then their neighbours, and so on. It uses a queue to remember which vertices to visit next.

Q: Write BFS in Java for a graph stored as an adjacency list.

Java example: import java.util.ArrayDeque; import java.util.ArrayList; import java.util.List; import java.util.Queue; static List bfs(List > graph, int start) { List order = new ArrayList<>(); boolean[] visited = new boolean[graph.size()]; Queue queue = new ArrayDeque<>(); visited[start] = true; queue.offer(start); while (!queue.isEmpty()) { int v = queue.poll(); order.add(v); for (int next : graph.get(v)) { if (!visited[next]) { visited[next] = true; // mark when added, not when removed queue.offer(next); } } } return order; }

Q: What is the time and space complexity of BFS?

Time: O(V + E) with an adjacency list, O(V 2 ) with a matrix. Space: O(V) for the queue and the visited array.

Q: Write a Java method that returns the shortest path itself using BFS.

Java example: import java.util.ArrayDeque; import java.util.Arrays; import java.util.LinkedList; import java.util.List; import java.util.Queue; static List shortestPath(List > graph, int from, int to) { int[] parent = new int[graph.size()]; Arrays.fill(parent, -1); boolean[] visited = new boolean[graph.size()]; Queue queue = new ArrayDeque<>(); visited[from] = true; queue.offer(from); while (!queue.isEmpty()) { int v = queue.poll(); if (v == to) break; for (int next : graph.get(v)) { if (!visited[next]) { visited[next] = true; parent[next] = v; // remember how we

Q: Write a Java program that runs BFS on a small graph and prints the order.

Java example: import java.util.ArrayDeque; import java.util.List; import java.util.Queue; public class BfsDemo { public static void main(String[] args) { List > graph = List.of( List.of(1, 2), // 0 List.of(0, 3), // 1 List.of(0, 3), // 2 List.of(1, 2) // 3 ); boolean[] visited = new boolean[graph.size()]; Queue queue = new ArrayDeque<>(); visited[0] = true; queue.offer(0); while (!queue.isEmpty()) { int v = queue.poll(); System.out.print(v + " "); for (int next : graph.get(v)) { if (!visited[next]) { visited[next] = true; queue.offer(next); } } } // Output: 0 1 2 3 } }

Breadth First Search (BFS) Algorithm

Graph traversal is a technique for searching a vertex in a graph. It can also be used to determine the order in which vertices are visited during the search process. Graph traversal determines which edges to use during the search process so as to avoid loops.

There are the following two possible way of graph traversal:

Breadth First Search (BFS)
Depth First Search (DFS)

In the graph tutorial, we are going learn all about Breadth First Search (BFS).

What is Breadth First Search (BFS)?

Breadth First Search (BFS) is a graph traversal algorithm. BFS first traverse all the neighboring nodes of the starting node once all neighboring nodes are visited, then it will move on to the next level as given in the image below.

BFS traversal of a graph produces a spanning tree as final result. Spanning Tree is a graph without loops.

BFS is the foundation of numerous well-known graph algorithms, including Prim's algorithm, Dijkstra's shortest path, and Kahn's algorithm.

How Breadth First Search (BFS) Works

Starting Node: Traversing begings from the staring node of the graph.
Queue: Create a queue to store nodes to be visited.
Visit: Mark the starting node as visited and enqueue it.
Dequeue and Explore:
- Dequeue the first node from the queue.
- Visit all unvisited neighbors of the dequeued node.
- Mark each visited neighbor as visited and enqueue it.
Repeat: Continue steps 4 and 5 until the queue is empty or the target node is found.

Example of BFS (Breadth First Search)

BFSExample.java

public class BFSExample {
  // BFS from given source s
  static void bfs(List<List<Integer>> adj, int s, boolean[] visited) {

    // Create a queue for BFS
    Queue<Integer> q = new LinkedList<>();

    // Mark the source node as visited and enqueue it
    visited[s] = true;
    q.offer(s);

    // Iterate over the queue
    while (!q.isEmpty()) {

      // Dequeue a vertex from queue and print it
      int curr = q.poll();
      System.out.print(curr + " ");

      // Get all adjacent vertices of the dequeued vertex.
      // If an adjacent has not been visited, mark it visited and enqueue it
      for (int x : adj.get(curr)) {
        if (!visited[x]) {
          visited[x] = true;
          q.offer(x);
        }
      }
    }
  }

  // Function to add an edge to the graph
  static void addEdge(List<List<Integer>> adj, int u, int v) {
    adj.get(u).add(v);
    adj.get(v).add(u);
  }

  public static void main(String[] args) {
    // Number of vertices in the graph
    int V = 5;

    // Adjacency list representation of the graph
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < V; i++) {
      adj.add(new ArrayList<>());
    }

    // Add edges to the graph
    addEdge(adj, 0, 1);
    addEdge(adj, 0, 2);
    addEdge(adj, 1, 3);
    addEdge(adj, 1, 4);
    addEdge(adj, 2, 4);

    // Mark all the vertices as not visited
    boolean[] visited = new boolean[V];

    // Perform BFS traversal starting from vertex 0
    System.out.println("BFS starting from node 0 : ");
    bfs(adj, 0, visited);
  }
}

Output

BFS starting from node 0 :

0 1 2 3 4

Time Complexity: O(V+E), where V is the number of nodes and E is the number of edges.

Auxiliary Space: O(V)

Frequently Asked Questions (FAQ)

Q1. What is breadth-first search?

Breadth-first search (BFS) explores a graph level by level: first the start vertex, then all its neighbours, then their neighbours, and so on. It uses a queue to remember which vertices to visit next.

Q2. Write BFS in Java for a graph stored as an adjacency list.

Bfs.java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

static List<Integer> bfs(List<List<Integer>> graph, int start) {
    List<Integer> order = new ArrayList<>();
    boolean[] visited = new boolean[graph.size()];
    Queue<Integer> queue = new ArrayDeque<>();
    visited[start] = true;
    queue.offer(start);
    while (!queue.isEmpty()) {
        int v = queue.poll();
        order.add(v);
        for (int next : graph.get(v)) {
            if (!visited[next]) {
                visited[next] = true;    // mark when added, not when removed
                queue.offer(next);
            }
        }
    }
    return order;
}

Q3. Why should a vertex be marked visited when it is added to the queue?

If you mark it only when it is removed, the same vertex can be added to the queue several times by different neighbours. That wastes time and memory and can produce duplicates in the output.

Q4. What is the time and space complexity of BFS?

Time: O(V + E) with an adjacency list, O(V²) with a matrix. Space: O(V) for the queue and the visited array.

Q5. Why does BFS find the shortest path in an unweighted graph?

BFS visits all vertices at distance 1 before any at distance 2, and so on. The first time it reaches a vertex is therefore along a path with the fewest edges.

Q6. Write a Java method that returns the shortest path itself using BFS.

BfsPath.java

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

static List<Integer> shortestPath(List<List<Integer>> graph, int from, int to) {
    int[] parent = new int[graph.size()];
    Arrays.fill(parent, -1);
    boolean[] visited = new boolean[graph.size()];
    Queue<Integer> queue = new ArrayDeque<>();
    visited[from] = true;
    queue.offer(from);
    while (!queue.isEmpty()) {
        int v = queue.poll();
        if (v == to) break;
        for (int next : graph.get(v)) {
            if (!visited[next]) {
                visited[next] = true;
                parent[next] = v;           // remember how we got here
                queue.offer(next);
            }
        }
    }
    LinkedList<Integer> path = new LinkedList<>();
    if (!visited[to]) return path;          // unreachable
    for (int v = to; v != -1; v = parent[v]) {
        path.addFirst(v);
    }
    return path;
}

Q7. Can BFS find the shortest path in a weighted graph?

No, not in general. BFS counts edges, not weights, so a path with fewer but heavier edges may be chosen. Use Dijkstra's algorithm for non-negative weights. (If every weight is 0 or 1, a variant called 0-1 BFS works with a deque.)

Q8. How do you run BFS on a graph that is not connected?

Loop over all vertices and start a new BFS from each one that has not been visited yet. Each new start discovers one connected component.

Q9. Where is BFS used?

Shortest paths in unweighted graphs and grids.
Finding friends within k connections in a social network.
Web crawlers that explore links level by level.
Checking whether a graph is bipartite.
Level order traversal of trees.

Q10. Write a Java program that runs BFS on a small graph and prints the order.

BfsDemo.java

import java.util.ArrayDeque;
import java.util.List;
import java.util.Queue;

public class BfsDemo {
    public static void main(String[] args) {
        List<List<Integer>> graph = List.of(
            List.of(1, 2),      // 0
            List.of(0, 3),      // 1
            List.of(0, 3),      // 2
            List.of(1, 2)       // 3
        );
        boolean[] visited = new boolean[graph.size()];
        Queue<Integer> queue = new ArrayDeque<>();
        visited[0] = true;
        queue.offer(0);
        while (!queue.isEmpty()) {
            int v = queue.poll();
            System.out.print(v + " ");
            for (int next : graph.get(v)) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.offer(next);
                }
            }
        }
        // Output: 0 1 2 3
    }
}

Was this tutorial helpful?

Help Us Improve

Breadth First Search (BFS) Algorithm

What is Breadth First Search (BFS)?

How Breadth First Search (BFS) Works

Example of BFS (Breadth First Search)

Frequently Asked Questions (FAQ)