C Program to Implement Breadth-First Search (BFS)

Introduction

Breadth-First Search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at a given node (usually called the root in the case of trees) and explores all its neighboring nodes at the present depth before moving on to nodes at the next depth level. BFS is particularly useful for finding the shortest path in an unweighted graph and for level-order traversal of a tree.

Example:

• Graph Structure:

  1 - 2
  |   |
  3 - 4
  

• BFS Output starting from Node 1: 1 2 3 4

Problem Statement

Create a C program that:

• Implements the Breadth-First Search algorithm for a graph.
• Traverses the graph using BFS and outputs the nodes in the order they are visited.

Solution Steps

1. Include the Standard Libraries: Use #include <stdio.h>, #include <stdlib.h>, and #include <stdbool.h> for standard input-output, memory allocation, and boolean types, respectively.
2. Define the Structure for the Graph: Use an adjacency list to represent the graph.
3. Implement the BFS Function: This function will traverse the graph using BFS starting from a given node.
4. Create a Main Function: Build a sample graph and perform BFS traversal.

C Program to Implement Breadth-First Search (BFS)

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

#define MAX 100  // Maximum number of vertices

// Structure to represent a queue
struct Queue {
    int items[MAX];
    int front;
    int rear;
};

// Function to create a queue
struct Queue* createQueue() {
    struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
    q->front = -1;
    q->rear = -1;
    return q;
}

// Function to check if the queue is empty
bool isEmpty(struct Queue* q) {
    return q->rear == -1;
}

// Function to enqueue an element to the queue
void enqueue(struct Queue* q, int value) {
    if (q->rear == MAX - 1)
        printf("\nQueue is full!!");
    else {
        if (q->front == -1)
            q->front = 0;
        q->rear++;
        q->items[q->rear] = value;
    }
}

// Function to dequeue an element from the queue
int dequeue(struct Queue* q) {
    int item;
    if (isEmpty(q)) {
        printf("Queue is empty");
        item = -1;
    } else {
        item = q->items[q->front];
        q->front++;
        if (q->front > q->rear) {
            q->front = q->rear = -1;
        }
    }
    return item;
}

// Function to print the queue
void printQueue(struct Queue* q) {
    int i = q->front;

    if (isEmpty(q)) {
        printf("Queue is empty");
    } else {
        printf("Queue contains:\n");
        for (i = q->front; i < q->rear + 1; i++) {
            printf("%d ", q->items[i]);
        }
    }
}

// Structure to represent a graph
struct Graph {
    int numVertices;
    int** adjMatrix;
    bool* visited;
};

// Function to create a graph
struct Graph* createGraph(int vertices) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->numVertices = vertices;

    graph->adjMatrix = (int**)malloc(vertices * sizeof(int*));
    for (int i = 0; i < vertices; i++) {
        graph->adjMatrix[i] = (int*)malloc(vertices * sizeof(int));
        for (int j = 0; j < vertices; j++) {
            graph->adjMatrix[i][j] = 0;
        }
    }

    graph->visited = (bool*)malloc(vertices * sizeof(bool));
    for (int i = 0; i < vertices; i++) {
        graph->visited[i] = false;
    }

    return graph;
}

// Function to add an edge to the graph
void addEdge(struct Graph* graph, int src, int dest) {
    graph->adjMatrix[src][dest] = 1;
    graph->adjMatrix[dest][src] = 1;  // If the graph is undirected
}

// Function to perform BFS traversal
void bfs(struct Graph* graph, int startVertex) {
    struct Queue* q = createQueue();

    graph->visited[startVertex] = true;
    enqueue(q, startVertex);

    while (!isEmpty(q)) {
        int currentVertex = dequeue(q);
        printf("%d ", currentVertex);

        for (int i = 0; i < graph->numVertices; i++) {
            if (graph->adjMatrix[currentVertex][i] == 1 && !graph->visited[i]) {
                graph->visited[i] = true;
                enqueue(q, i);
            }
        }
    }
}

int main() {
    int vertices = 4;

    // Create a graph with 4 vertices
    struct Graph* graph = createGraph(vertices);

    // Add edges
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);

    // Perform BFS traversal starting from vertex 0
    printf("Breadth-First Search starting from vertex 0:\n");
    bfs(graph, 0);

    return 0;  // Return 0 to indicate successful execution
}

Explanation

Structure for the Queue

• The struct Queue represents a simple queue used to manage the vertices during BFS traversal. It includes functions to enqueue, dequeue, and check if the queue is empty.

Structure for the Graph

• The struct Graph represents the graph using an adjacency matrix and a visited array to keep track of visited vertices.

Function to Create a Graph

• The createGraph function initializes the adjacency matrix and the visited array for the specified number of vertices.

Function to Add an Edge

• The addEdge function adds an undirected edge between two vertices by updating the adjacency matrix.

Function to Perform BFS Traversal

• The bfs function performs BFS traversal starting from the specified vertex. It uses a queue to explore all neighbors of a vertex before moving to the next vertex.

Main Function

• The main function creates a sample graph with 4 vertices, adds edges, and then performs BFS starting from vertex 0.

Output Example

Example Output:

Breadth-First Search starting from vertex 0:
0 1 2 3

Conclusion

This C program demonstrates how to implement Breadth-First Search (BFS) for a graph using an adjacency matrix. BFS is a fundamental graph traversal algorithm, widely used for searching and exploring graphs in various applications. This program provides a practical example of how BFS can be implemented and applied in C programming.