C Program: Breadth-First Search (BFS)

This C program demonstrates the Breadth-First Search (BFS) algorithm in a graph. The BFS algorithm is used to traverse or search tree or graph data structures. It starts at a given node (often called the ‘root’ node) and explores all of the neighbor nodes at the present depth prior to moving on to nodes at the next depth level.

Program Explanation

The program includes a Graph structure which represents the graph structure and contains functions to add edges and perform BFS traversal.

Key components of the program include:

• The Graph structure which uses an array of linked lists to represent the adjacency list of each vertex.
• The addEdge function to add edges between vertices in the graph.
• The BFS function to perform the BFS traversal starting from a given vertex.
• The main function to create the graph, add edges, and initiate the BFS traversal.

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

#define MAX_VERTICES 100

// Structure to represent a node in the adjacency list
struct Node {
    int vertex;
    struct Node* next;
};

// Structure to represent a graph
struct Graph {
    int numVertices;
    struct Node* adjLists[MAX_VERTICES];
    bool visited[MAX_VERTICES];
};

// Function to create a node
struct Node* createNode(int v) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

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

    for (int i = 0; i < vertices; i++) { graph->adjLists[i] = NULL;
        graph->visited[i] = false;
    }
    return graph;
}

// Function to add an edge to the graph
void addEdge(struct Graph* graph, int src, int dest) {
    // Add edge from src to dest
    struct Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // Add edge from dest to src (for undirected graph)
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

// Function to perform BFS
void BFS(struct Graph* graph, int startVertex) {
    struct Node* queue[MAX_VERTICES];
    int front = 0, rear = 0;

    graph->visited[startVertex] = true;
    queue[rear++] = createNode(startVertex);

    while (front < rear) { struct Node* currentNode = queue[front++]; int currentVertex = currentNode->vertex;
        printf("%d ", currentVertex);

        struct Node* temp = graph->adjLists[currentVertex];
        while (temp) {
            int adjVertex = temp->vertex;
            if (!graph->visited[adjVertex]) {
                graph->visited[adjVertex] = true;
                queue[rear++] = createNode(adjVertex);
            }
            temp = temp->next;
        }
    }
}

int main() {
    struct Graph* graph = createGraph(6);

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 2, 4);
    addEdge(graph, 3, 4);
    addEdge(graph, 3, 5);

    printf("Breadth First Traversal starting from vertex 0:\n");
    BFS(graph, 0);

    return 0;
}