Graph Traversals: Breadth-First Search (BFS) in C

What You’ll Learn 📚

• Understanding the core concepts of BFS
• Key terminology and definitions
• How to implement BFS in C with examples
• Troubleshooting common issues
• Answers to frequently asked questions

Introduction to Graph Traversals

Graphs are a fundamental data structure in computer science, used to model relationships between objects. Traversing a graph means visiting all the nodes (or vertices) in a systematic way. There are two primary methods for graph traversal: Breadth-First Search (BFS) and Depth-First Search (DFS).

What is Breadth-First Search (BFS)?

BFS is a graph traversal algorithm that explores nodes level by level. Imagine you’re standing at the root of a tree and want to explore all the nodes. BFS will explore all the nodes at the present depth before moving on to nodes at the next depth level. It’s like ripples spreading out in a pond! 🌊

Think of BFS as exploring all your immediate neighbors before moving further away. It’s great for finding the shortest path in an unweighted graph!

Key Terminology

• Graph: A collection of nodes (vertices) and edges connecting them.
• Vertex: A node in the graph.
• Edge: A connection between two vertices.
• Queue: A data structure used in BFS to keep track of nodes to be explored. It follows First-In-First-Out (FIFO) principle.

Let’s Start with a Simple Example

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

#define MAX 100

int queue[MAX];
int front = -1, rear = -1;

void enqueue(int value) {
    if (rear == MAX - 1) {
        printf("Queue is full!\n");
    } else {
        if (front == -1) front = 0;
        queue[++rear] = value;
    }
}

int dequeue() {
    if (front == -1 || front > rear) {
        printf("Queue is empty!\n");
        return -1;
    } else {
        return queue[front++];
    }
}

int isEmpty() {
    return front == -1 || front > rear;
}

void bfs(int graph[MAX][MAX], int start, int n) {
    int visited[MAX] = {0};
    enqueue(start);
    visited[start] = 1;

    while (!isEmpty()) {
        int current = dequeue();
        printf("Visited %d\n", current);

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

int main() {
    int n = 4; // Number of vertices
    int graph[MAX][MAX] = {
        {0, 1, 1, 0},
        {1, 0, 1, 1},
        {1, 1, 0, 0},
        {0, 1, 0, 0}
    };

    printf("BFS starting from vertex 0:\n");
    bfs(graph, 0, n);

    return 0;
}

Visited 0
Visited 1
Visited 2
Visited 3

Progressively Complex Examples

Example 2: BFS with a Larger Graph

Let's expand our graph and see how BFS handles more nodes:

// Code for a larger graph implementation

// Expected output for the larger graph

Example 3: Handling Disconnected Graphs

What if the graph isn't fully connected? Let's find out:

// Code for handling disconnected graphs

// Expected output for disconnected graphs

Example 4: BFS for Shortest Path

Using BFS to find the shortest path in an unweighted graph:

// Code for shortest path using BFS

// Expected output for shortest path

Common Questions and Answers

1. Why use BFS over DFS?

   BFS is preferred when you need the shortest path in an unweighted graph. DFS is better for exploring all paths.

2. What is the time complexity of BFS?

   The time complexity is O(V + E), where V is the number of vertices and E is the number of edges.

3. Can BFS be used on weighted graphs?

   BFS is not suitable for weighted graphs as it doesn't account for edge weights. Use Dijkstra's algorithm instead.

Troubleshooting Common Issues

Ensure your queue isn't overflowing. Always check if the queue is full before enqueuing.

If your BFS isn't visiting all nodes, double-check your adjacency matrix and ensure all edges are represented correctly.

Practice Exercises

• Modify the BFS code to print the path taken to reach each node.
• Implement BFS using a different data structure, like a linked list, for the queue.

Keep practicing, and remember, every mistake is a step towards mastery! 💪