SYBCom(CA) DS Practical Slip 14 Q.A

Write a C program to traverse graph by using BFS.

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

#define MAX 100

int queue[MAX], front = -1, rear = -1;

// Function to enqueue
void enqueue(int value) {
    if(rear == MAX - 1) {
        printf("Queue Overflow\n");
        return;
    }
    if(front == -1) front = 0;
    queue[++rear] = value;
}

// Function to dequeue
int dequeue() {
    if(front == -1 || front > rear) {
        printf("Queue Underflow\n");
        return -1;
    }
    return queue[front++];
}

// Function to check if queue is empty
int isEmpty() {
    return (front == -1 || front > rear);
}

// BFS function
void BFS(int adj[MAX][MAX], int n, int start) {
    int visited[MAX] = {0};
    int i, current;

    enqueue(start);
    visited[start] = 1;

    printf("BFS Traversal starting from vertex %d:\n", start + 1);

    while(!isEmpty()) {
        current = dequeue();
        printf("%d ", current + 1);

        for(i = 0; i < n; i++) {
            if(adj[current][i] == 1 && !visited[i]) {
                enqueue(i);
                visited[i] = 1;
            }
        }
    }
    printf("\n");
}

int main() {
    int n, i, j;

    printf("Enter number of vertices: ");
    scanf("%d", &n);

    int adj[MAX][MAX];

    printf("Enter adjacency matrix (%dx%d):\n", n, n);
    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++)
            scanf("%d", &adj[i][j]);

    int start;
    printf("Enter starting vertex (1 to %d): ", n);
    scanf("%d", &start);

    BFS(adj, n, start - 1);  // array index starts from 0

    return 0;
}