C Programming - Breadth-First Search (BFS)

Welcome to our deep dive into the fascinating world of C Programming! Today, we'll be exploring the concept of Breadth-First Search (BFS), a popular graph traversal algorithm.

Let's start with the basics. In graph theory, we often find ourselves in situations where we need to traverse or explore a graph to find the shortest path, discover connected components, or even find the largest connected component. BFS is one of the simplest and most effective algorithms for achieving these tasks.

📝 Understanding BFS

BFS works by exploring all the vertices (nodes) at a given level before moving on to the next level. This is achieved by maintaining a queue of vertices to be explored.

Here's a simple step-by-step process of BFS:

Initialize a queue and a visited array.
Insert the start vertex into the queue and mark it as visited.
While the queue is not empty:
- Dequeue a vertex from the queue.
- Print the dequeued vertex.
- Traverse through all adjacent vertices of the dequeued vertex and add them to the queue if they are not already visited.
Once the loop ends, we have visited all vertices in the breadth-first order.

🎯 Implementing BFS in C

Let's write a simple C program to perform BFS on an adjacency matrix representation of a graph.

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 100

void bfs(int graph[MAX_VERTICES][MAX_VERTICES], int visited[], int source) {
    int queue[MAX_VERTICES];
    int front = 0, rear = -1;

    visited[source] = 1;
    queue[++rear] = source;

    while (front <= rear) {
        int current = queue[front++];
        printf("Visiting vertex %d\n", current);

        for (int i = 0; i < MAX_VERTICES; i++) {
            if (graph[current][i] && !visited[i]) {
                visited[i] = 1;
                queue[++rear] = i;
            }
        }
    }
}

int main() {
    int graph[MAX_VERTICES][MAX_VERTICES] = {
        {0, 1, 0, 0, 0, 0, 0, 1, 0, 0},
        {1, 0, 1, 1, 0, 1, 0, 1, 1, 0},
        {0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 1, 0, 0, 1, 1, 0, 0, 0, 0},
        {0, 0, 0, 1, 0, 1, 0, 1, 1, 1},
        {0, 1, 0, 1, 1, 0, 1, 0, 0, 0},
        {0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
        {1, 1, 0, 0, 1, 0, 0, 0, 1, 0},
        {0, 1, 0, 0, 1, 0, 0, 1, 0, 1},
        {0, 0, 0, 0, 1, 0, 0, 0, 1, 0}
    };

    int visited[MAX_VERTICES] = {0};
    bfs(graph, visited, 0);

    return 0;
}

This program will perform a BFS starting from vertex 0 and print the vertices in the order they are visited.

📝 BFS Applications

BFS has a variety of applications in real-world scenarios, including:

Shortest Path Finding: BFS can be used to find the shortest path between two vertices in a weighted graph.
Connected Components: BFS can be used to find the connected components of a graph.
Minimum Spanning Trees: BFS can be used to find the minimum spanning tree of a graph by Kruskal's algorithm.
Maze Solving: BFS can be used to find the shortest path from a start cell to an end cell in a maze.

💡 Pro Tip:

Remember to use BFS when you need to explore all vertices at a given level before moving on to the next level, and when you're dealing with unweighted graphs or when the shortest path is not critical.

✅ Quiz Time!

With this, we've covered the essentials of BFS in C Programming. As you delve deeper into the world of C, you'll find that BFS is a versatile and powerful tool for traversing graphs. Happy coding! 🚀