BFS ( Breadth First Search ) on a Graph

Given a directed or undirected graph, write a program to perform Breadth First Search (BFS) starting from a given source node. In BFS, we start from a node and explore all its neighbors first, before moving on to the next level of neighbors. The traversal explores nodes level by level.

Input/Output Examples

plaintext
Example 1 (Undirected Graph):
Input:

  0 --- 1
   |     \
   |      2
   |     /
  3 --- 4

Output: 0 1 3 2 4
Explanation: Starting from node 0, BFS explores nodes in breadth-first manner. The nodes are visited in the order 0 -> 1 -> 3 -> 2 -> 4.

Example 2 (Directed Graph):
Input:

    0
   / \
  1   2
   \   \
    3 - 4

Output: 0 1 2 3 4
Explanation: Starting from node 0, BFS explores nodes in breadth-first manner, visiting nodes in the order 0 -> 1 -> 2 -> 3 -> 4.

Approach to Perform Breadth First Search (BFS) on a Graph

  1. Graph Representation:
    • We represent a graph using an adjacency list, where each node points to a list of its adjacent nodes (neighbors).
    • The graph can be either directed or undirected. In both cases, BFS will visit all nodes reachable from the starting node.
  2. BFS Using a Queue:
    • Start from the given source node.
    • Use a queue to keep track of nodes to visit.
    • Visit the node at the front of the queue and enqueue all its unvisited neighbors.
    • Continue until the queue is empty.
  3. Handling Disconnected Components:
    • In a graph, it’s possible that not all nodes are reachable from the starting node. To handle disconnected components, we can check if all nodes have been visited and perform BFS for each unvisited node.
  4. Edge Cases:
    • If the graph is empty, return an empty traversal.
    • If the graph has only one node, return that node as the traversal.

C++ Program for Breadth First Search of a Graph

cpp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// Function to perform BFS traversal on a graph
void bfs(int start, vector<int> adj[], vector<bool>& visited) {
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " ";  // Visit the node

        // Explore all neighbors of the current node
        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

int main() {
    // Number of vertices
    int V = 5;
    
    // Create an adjacency list for the graph
    vector<int> adj[V];

    // Adding edges (Undirected graph)
    adj[0].push_back(1);
    adj[1].push_back(0);
    
    adj[0].push_back(3);
    adj[3].push_back(0);
    
    adj[1].push_back(2);
    adj[2].push_back(1);
    
    adj[1].push_back(4);
    adj[4].push_back(1);
    
    adj[3].push_back(4);
    adj[4].push_back(3);

    vector<bool> visited(V, false);

    // Perform BFS starting from node 0
    cout << "BFS Traversal starting from node 0: ";
    bfs(0, adj, visited);
    cout << endl;

    return 0;
}

Java Program for Breadth First Search of a Graph

java
import java.util.*;

// BFS Traversal on a Graph
public class BFSGraph {

    // Function to perform BFS traversal on the graph
    public static void bfs(int start, List<List<Integer>> adj, boolean[] visited) {
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        visited[start] = true;

        while (!q.isEmpty()) {
            int node = q.poll();
            System.out.print(node + " ");  // Visit the node

            // Explore all neighbors of the current node
            for (int neighbor : adj.get(node)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.add(neighbor);
                }
            }
        }
    }

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

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

        // Adding edges (Undirected graph)
        adj.get(0).add(1);
        adj.get(1).add(0);
        
        adj.get(0).add(3);
        adj.get(3).add(0);
        
        adj.get(1).add(2);
        adj.get(2).add(1);
        
        adj.get(1).add(4);
        adj.get(4).add(1);
        
        adj.get(3).add(4);
        adj.get(4).add(3);

        boolean[] visited = new boolean[V];

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

Python Program for Breadth First Search of a Graph

python
from collections import deque

# Function to perform BFS traversal on a graph
def bfs(start, adj, visited):
    q = deque([start])
    visited[start] = True

    while q:
        node = q.popleft()
        print(node, end=" ")  # Visit the node

        # Explore all neighbors of the current node
        for neighbor in adj[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                q.append(neighbor)

# Example usage
if __name__ == "__main__":
    # Number of vertices
    V = 5

    # Create an adjacency list for the graph
    adj = [[] for _ in range(V)]

    # Adding edges (Undirected graph)
    adj[0].append(1)
    adj[1].append(0)
    
    adj[0].append(3)
    adj[3].append(0)
    
    adj[1].append(2)
    adj[2].append(1)
    
    adj[1].append(4)
    adj[4].append(1)
    
    adj[3].append(4)
    adj[4].append(3)

    visited = [False] * V

    # Perform BFS starting from node 0
    print("BFS Traversal starting from node 0:", end=" ")
    bfs(0, adj, visited)
    print()
  • Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges. Each vertex and each edge is processed once during the traversal.
  • Space Complexity: O(V) for the visited array and the queue.

DSA

8851

614

Related Articles