1// Aim: Program to perform Breadth First Search (BFS) on a graph.
2#include <stdio.h>
3#include <stdlib.h>
4
5#define MAX 20
6int q[MAX], f = -1, r = -1, nv, am[MAX][MAX], visited[MAX];
7
8void enqueue(int item) 
9{
10    if (r==MAX)
11    {
12        printf("Queue overflow\n");
13        return;
14    }
15    if (f == -1)
16    {  
17        f = r = 0;
18    }
19    else 
20    {
21        r++;  
22    }
23    q[r] = item;
24}
25
26int dequeue() 
27{
28    if (f == -1)
29    {
30        printf("Queue is empty\n");
31        return -1;  
32    }
33    int item = q[f];
34    if (f == r) 
35    {  
36        f = r = -1; 
37    } else
38    {
39        f++;  
40    }
41    return item;
42}
43
44void bfs(int sv)
45{
46    visited[sv] = 1;
47    enqueue(sv);
48
49    printf("BFS Traversal: ");
50
51    while (f != -1) 
52    {
53        int cv = dequeue();
54        printf("v%d ", cv);
55
56        for (int i = 0; i < nv; i++)
57        {
58            if (am[cv][i] == 1 && visited[i] == 0)
59            {
60                visited[i] = 1;
61                enqueue(i);
62            }
63        }
64    }
65    printf("\n");
66}
67
68int main()
69{
70    int e, sv;
71    printf("Enter the number of vertices: ");
72    scanf("%d", &nv);
73
74    for (int i = 0; i < nv; i++)
75    {
76        visited[i] = 0;
77        for (int j = 0; j < nv; j++)
78        {
79            am[i][j] = 0;
80        }
81    }
82    for (int i = 0; i < nv; i++) 
83    {
84        for (int j = 0; j < nv; j++)
85        {
86            if (i != j) { 
87                printf("Do you want to create an edge between v%d and v%d? (enter 1 for yes, 0 for no): ", i, j);
88                scanf("%d", &e);
89                if (e == 1) 
90                {
91                    am[i][j] = 1;  
92                }
93            }
94        }
95    }
96
97    printf("Adjacency matrix:\n");
98    for (int i = 0; i < nv; i++) 
99    {
100        for (int j = 0; j < nv; j++) 
101        {
102            printf("%d ", am[i][j]);
103        }
104        printf("\n");
105    }
106    printf("Enter the starting vertex (0 to %d): ", nv - 1);
107    scanf("%d", &sv);
108
109    bfs(sv);
110    return 0;
111}