Breadth-First Search (BFS) Algorithm

1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5// Define the maximum number of vertices
6#define MAX_VERTICES 100
7
8// Graph represented as an adjacency list
9typedef struct {
10    int vertices;                // Number of vertices
11    int* adjacencyList[MAX_VERTICES]; // Array of adjacency lists
12    int size[MAX_VERTICES];      // Size of each adjacency list
13    int capacity[MAX_VERTICES];  // Capacity of each adjacency list
14} Graph;
15
16// Queue for BFS traversal
17typedef struct {
18    int items[MAX_VERTICES];
19    int front;
20    int rear;
21} Queue;
22
23// Initialize an empty queue
24Queue* createQueue() {
25    Queue* q = (Queue*)malloc(sizeof(Queue));
26    q->front = -1;
27    q->rear = -1;
28    return q;
29}
30
31// Check if the queue is empty
32bool isEmpty(Queue* q) {
33    return q->front == -1;
34}
35
36// Add element to the queue
37void enqueue(Queue* q, int value) {
38    if (q->rear == MAX_VERTICES - 1)
39        printf("Queue is full\n");
40    else {
41        if (q->front == -1)
42            q->front = 0;
43        q->rear++;
44        q->items[q->rear] = value;
45    }
46}
47
48// Remove element from the queue
49int dequeue(Queue* q) {
50    int item;
51    if (isEmpty(q)) {
52        printf("Queue is empty\n");
53        return -1;
54    } else {
55        item = q->items[q->front];
56        q->front++;
57        if (q->front > q->rear) {
58            q->front = -1;
59            q->rear = -1;
60        }
61        return item;
62    }
63}
64
65// Initialize a graph with n vertices
66Graph* createGraph(int vertices) {
67    Graph* graph = (Graph*)malloc(sizeof(Graph));
68    graph->vertices = vertices;
69    
70    for (int i = 0; i < vertices; i++) {
71        graph->adjacencyList[i] = (int*)malloc(sizeof(int));
72        graph->size[i] = 0;
73        graph->capacity[i] = 1;
74    }
75    
76    return graph;
77}
78
79// Add an edge to the graph
80void addEdge(Graph* graph, int src, int dest) {
81    // Add edge from src to dest
82    if (graph->size[src] == graph->capacity[src]) {
83        graph->capacity[src] *= 2;
84        graph->adjacencyList[src] = (int*)realloc(graph->adjacencyList[src], graph->capacity[src] * sizeof(int));
85    }
86    graph->adjacencyList[src][graph->size[src]++] = dest;
87    
88    // Add edge from dest to src (for undirected graph)
89    if (graph->size[dest] == graph->capacity[dest]) {
90        graph->capacity[dest] *= 2;
91        graph->adjacencyList[dest] = (int*)realloc(graph->adjacencyList[dest], graph->capacity[dest] * sizeof(int));
92    }
93    graph->adjacencyList[dest][graph->size[dest]++] = src;
94}
95
96// BFS traversal of the graph starting from vertex s
97void BFS(Graph* graph, int startVertex) {
98    // Mark all vertices as not visited
99    bool visited[MAX_VERTICES] = {false};
100    
101    // Create a queue for BFS
102    Queue* q = createQueue();
103    
104    // Mark the current node as visited and enqueue it
105    visited[startVertex] = true;
106    enqueue(q, startVertex);
107    
108    printf("BFS traversal starting from vertex %d: ", startVertex);
109    
110    while (!isEmpty(q)) {
111        // Dequeue a vertex from queue and print it
112        int currentVertex = dequeue(q);
113        printf("%d ", currentVertex);
114        
115        // Get all adjacent vertices of the dequeued vertex
116        // If an adjacent has not been visited, mark it visited and enqueue it
117        for (int i = 0; i < graph->size[currentVertex]; i++) {
118            int adjacentVertex = graph->adjacencyList[currentVertex][i];
119            if (!visited[adjacentVertex]) {
120                visited[adjacentVertex] = true;
121                enqueue(q, adjacentVertex);
122            }
123        }
124    }
125    printf("\n");
126    
127    free(q);
128}
129
130// Driver program
131int main() {
132    // Create a graph with 5 vertices
133    Graph* graph = createGraph(5);
134    
135    // Add edges (representing the example graph in the visual)
136    addEdge(graph, 0, 1); // A - B
137    addEdge(graph, 0, 2); // A - C
138    addEdge(graph, 1, 3); // B - D
139    addEdge(graph, 2, 4); // C - E
140    
141    // Perform BFS starting from vertex 0 (A)
142    BFS(graph, 0);
143    
144    // Free allocated memory
145    for (int i = 0; i < graph->vertices; i++) {
146        free(graph->adjacencyList[i]);
147    }
148    free(graph);
149    
150    return 0;
151}