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:

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

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

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

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

6 5
0 1
0 2
1 3
3 4
4 5

Output

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.