Breadth First Search (BFS) Algorithm

Last Updated: 06 October, 2024 🕓 5 Mins

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:

Example of BFS (Breadth First Search)

  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);
    }
  }

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