BFS Graph Exploration: C++ Implementation Guide

Graphs are one of the most versatile data structures in computer science, used to model relationships and connections. Breadth-First Search (BFS) is a powerful algorithm for exploring a graph level by level. This blog delves into the BFS implementation in C++, providing a practical example of traversing an undirected graph using an adjacency matrix.

Understanding the Code: BFS Implementation

The given code demonstrates how to perform a BFS traversal on an undirected graph. Here's a breakdown of the implementation:

Step 1: Setting Up the Graph

The graph is represented using an adjacency matrix, a 2D array where graph[i][j] = 1 indicates a direct edge between vertices i and j. The program dynamically allocates memory for the adjacency matrix based on user input.

int V, E;
cin >> V >> E;
int** graph = new int*[V];
for(int i=0; i<V; i++) {
    graph[i] = new int[V];
    for(int j=0; j<V; j++) graph[i][j] = 0;
}

Here:

V is the number of vertices.
E is the number of edges.

The user inputs the edges, and the adjacency matrix is updated accordingly:

for(int i=0; i<E; i++) {
    int a, b;
    cin >> a >> b;
    graph[a][b] = graph[b][a] = 1;
}

Step 2: Initializing the Visited Array

An array visited keeps track of which vertices have already been explored to avoid processing the same vertex multiple times.

cppCopy codeint* visited = new int[V];
for(int i=0; i<V; i++) visited[i] = 0;

Step 3: BFS Traversal

The core of the BFS algorithm lies in the function bfs_print. Here's the step-by-step logic:

Function Definition

void bfs_print(int** graph, int V, int sv, int* visited) {
    queue<int> q;
    q.push(sv);
    visited[sv] = 1;
    while(!q.empty()) {
        int t = q.front();
        q.pop();
        cout << t << " ";
        for(int i=0; i<V; i++) {
            if(i == t) continue;
            if(graph[t][i] && !visited[i]) {
                visited[i] = 1;
                q.push(i);
            }
        }
    }
}

Key Steps in BFS

Initialization: Start with a queue and enqueue the source vertex (sv). Mark it as visited.
```
 queue<int> q;
 q.push(sv);
 visited[sv] = 1;
```
Processing Vertices: Dequeue a vertex, print it, and enqueue all its unvisited neighbors.
```
 int t = q.front();
 q.pop();
 cout << t << " ";
```
Enqueue Neighbors: Check all vertices connected to the current vertex (t) and add unvisited ones to the queue.
```
 if(graph[t][i] && !visited[i]) {
     visited[i] = 1;
     q.push(i);
 }
```

Step 4: Running the Program

Input the number of vertices (V), edges (E), and the edges themselves in the format (a, b).

Sample Input

Sample Output

0 1 2 3 4 5

How It Works

The BFS starts at the vertex 0.
It explores all direct neighbors of 0 (vertices 1 and 2).
Then, it moves to the next level, exploring neighbors 1 and 2 that haven’t been visited, and so on.

Advantages of BFS

Level-wise Traversal: BFS is ideal for finding the shortest path in an unweighted graph.
Queue-based Approach: The algorithm ensures that each vertex is processed only once.

Complexity Analysis

Time Complexity: O(V^2) for adjacency matrix representation, where V is the number of vertices.
Space Complexity: O(V) for the visited array and the queue.

Conclusion

This BFS implementation serves as a foundational step in mastering graph traversal techniques. Whether you're solving real-world problems like social network analysis or preparing for coding interviews, understanding BFS is essential. Experiment with the code, and try adapting it to explore more complex graph problems!

References

Find the code for the above explanation here.

Exploring Graphs with BFS: A Hands-On Implementation in C++

Table of contents