bfs

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

// Define the maximum number of vertices in the graph
#define MAX_VERTICES 100

// Define a queue structure for BFS
struct Queue {
    int front, rear, size;
    unsigned capacity;
    int* array;
};

// Function to create a new queue
struct Queue* createQueue(unsigned capacity) {
    struct Queue queue = (struct Queue)malloc(sizeof(struct Queue));
    queue->capacity = capacity;
    queue->front = queue->size = 0;
    queue->rear = capacity - 1;
    queue->array = (int)malloc(queue->capacity  sizeof(int));
    return queue;
}

// Function to check if the queue is empty
int isEmpty(struct Queue* queue) {
    return (queue->size == 0);
}

// Function to check if the queue is full
int isFull(struct Queue* queue) {
    return (queue->size == queue->capacity);
}

// Function to enqueue a vertex to the queue
void enqueue(struct Queue* queue, int item) {
    if (isFull(queue))
        return;
    queue->rear = (queue->rear + 1) % queue->capacity;
    queue->array[queue->rear] = item;
    queue->size = queue->size + 1;
}

// Function to dequeue a vertex from the queue
int dequeue(struct Queue* queue) {
    if (isEmpty(queue))
        return -1;
    int item = queue->array[queue->front];
    queue->front = (queue->front + 1) % queue->capacity;
    queue->size = queue->size - 1;
    return item;
}

// Function to perform BFS traversal on a graph
void BFS(int graph[MAX_VERTICES][MAX_VERTICES], int startVertex, int numVertices) {
    // Create a queue for BFS
    struct Queue* queue = createQueue(MAX_VERTICES);

    // Mark all vertices as not visited
    int visited[MAX_VERTICES];
    for (int i = 0; i < numVertices; i++)
        visited[i] = 0;

    // Enqueue the starting vertex and mark it as visited
    enqueue(queue, startVertex);
    visited[startVertex] = 1;

    // Perform BFS
    while (!isEmpty(queue)) {
        // Dequeue a vertex and print it
        int currentVertex = dequeue(queue);
        printf("%d ", currentVertex);

        // Enqueue all adjacent vertices of the dequeued vertex that have not been visited
        for (int i = 0; i < numVertices; i++) {
            if (graph[currentVertex][i] == 1 && !visited[i]) {
                enqueue(queue, i);
                visited[i] = 1;
            }
        }
    }

    // Free the memory allocated for the queue
    free(queue->array);
    free(queue);
}

int main() {
    // Define a sample graph as an adjacency matrix
    int graph[MAX_VERTICES][MAX_VERTICES] = {
        {0, 1, 1, 0, 0},
        {1, 0, 0, 1, 1},
        {1, 0, 0, 0, 1},
        {0, 1, 0, 0, 1},
        {0, 1, 1, 1, 0}
    };

    // Set the number of vertices in the graph
    int numVertices = 5;

    // Set the starting vertex for BFS
    int startVertex = 0;

    // Perform BFS traversal starting from the specified vertex
    printf("BFS Traversal starting from vertex %d: ", startVertex);
    BFS(graph, startVertex, numVertices);

    return 0;
}