#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;
}