# Exploring Graphs with Breadth-First Search (BFS) in C++

Graphs are fundamental structures in computer science, representing networks such as social connections, web pages, or city maps. One popular way to traverse graphs is through **Breadth-First Search (BFS)**, a systematic level-by-level exploration method. This blog dives into BFS, implemented in C++, to traverse a graph and handle disconnected components.

### Understanding the Code

#### **Key Concepts**

1. **Graph Representation**: The graph is represented as an adjacency matrix, where `graph[i][j]` indicates a connection between nodes `i` and `j`.
    
2. **BFS Basics**: BFS uses a queue to explore all neighboring nodes of a starting vertex before moving to the next level of neighbors.
    
3. **Disconnected Graphs**: This implementation ensures all components of the graph are visited, even if the graph is disconnected.
    

### **Code Walkthrough**

#### **Graph Representation**

The graph is initialized as an adjacency matrix:

```cpp
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, and `E` is the number of edges. The adjacency matrix is populated based on input edges.

#### **Core BFS Logic**

##### `bfs_print`

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

* **Inputs:**
    
    * `graph`: Adjacency matrix of the graph.
        
    * `V`: Total vertices in the graph.
        
    * `sv`: Starting vertex for BFS.
        
    * `visited`: Array to track visited nodes.
        
* **How it works:**
    
    * The function uses a queue to process nodes.
        
    * Starting from `sv`, it marks the node as visited and enqueues it.
        
    * For each dequeued node, all unvisited neighbors are enqueued.
        

##### `bfs`

```cpp
void bfs(int** graph, int V, int sv){
    int* visited = new int[V];
    for(int i=0;i<V;i++) visited[i] = 0;
    for(int i=0;i<V;i++){
        if(!visited[i]){
            bfs_print(graph, V, i, visited);
        }
    }
}
```

* Ensures all nodes, including those in disconnected components, are visited.
    
* Calls `bfs_print` for each unvisited node.
    

#### **Main Function**

```cpp
int main() {
    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;
    }
    for(int i=0;i<E;i++){
        int a, b;
        cin >> a >> b;
        graph[a][b] = graph[b][a] = 1;
    }
    
    bfs(graph, V, 0);
    return 0;
}
```

* Reads the number of vertices (`V`) and edges (`E`).
    
* Populates the adjacency matrix with edge connections.
    
* Calls `bfs` to traverse the graph starting from vertex 0.
    

### Example Input/Output

#### **Input**

```bash
6 5
0 1
0 2
1 3
3 4
4 5
```

#### **Output**

```bash
0 1 2 3 4 5
```

#### Explanation:

* The BFS traversal starts at the vertex `0` and explores all reachable nodes.
    

### Key Advantages

* **Handles Disconnected Graphs**: The `bfs` function ensures even isolated components are traversed.
    
* **Simple Implementation**: The adjacency matrix and queue make the traversal easy to implement and debug.
    

### Optimizations and Notes

1. **Space Efficiency**: For sparse graphs, use adjacency lists instead of matrices to save memory.
    
2. **Edge Cases**:
    
    * A graph with no edges.
        
    * Graphs with multiple disconnected components.
        

### Conclusion

BFS is a versatile algorithm for graph traversal, finding applications in shortest-path problems, network analysis, and more. The above implementation serves as a strong foundation for exploring more advanced graph algorithms.

## **References**

1. Find the code for the above explanation [**here**](https://github.com/tanaytoshniwal/Data-Structures-Algorithms/blob/master/Data%20Structures/Graphs/bfs_disconnected_graph.cpp).