//BFS TRAVERSAL
//Aim: implement the breadth first search traversal algorithm on graph

#include <stdio.h>
#define MAX 20
int queue[MAX];
int front = -1, rear = -1;
void enqueue(int item) {
 if (rear == MAX - 1)
 printf("Queue Overflow\n");
 else {
 if (front == -1)
 front = 0;
 rear = rear + 1;
 queue[rear] = item;
 }
}
int dequeue() {
 int item;
 if (front == -1 || front > rear) {
 printf("Queue Underflow\n");
 return -1;
 } else {
 item = queue[front];
 front = front + 1;
 return item;
 }
}
int isEmpty() {
 if (front == -1 || front > rear)
 return 1;
 else
 return 0;
}
void bfs(int adj_matrix[][MAX], int visited[], int start, int n) {
 int i, current;
 visited[start] = 1;
 enqueue(start);
 while (!isEmpty()) {
 current = dequeue();
 printf("%d ", current + 1); // Printing vertex numbers (assuming vertices are numbered from 1 to n)
 for (i = 0; i < n; i++) {
 if (adj_matrix[current][i] == 1 && !visited[i]) {
 enqueue(i);
 visited[i] = 1;
 }
 }
 }
}
int main() {
 int adj_matrix[MAX][MAX], visited[MAX];
 int n, i, j, start_vertex;
 printf("Enter the number of vertices: ");
 scanf("%d", &n);
 printf("Enter the adjacency matrix (1 for edge, 0 otherwise):\n");
 for (i = 0; i < n; i++) {
 for (j = 0; j < n; j++) {
 printf("Is there an edge between vertex %d and vertex %d? (1/0): ", i + 1, j + 1);
 scanf("%d", &adj_matrix[i][j]);
 }
 }
 for (i = 0; i < n; i++)
 visited[i] = 0;
 printf("Enter the starting vertex: ");
 scanf("%d", &start_vertex);
 printf("BFS Traversal: ");
 bfs(adj_matrix, visited, start_vertex - 1, n); // Adjusting the vertex index to 0-based
 return 0;
}