#include <stdio.
h>
#include <conio.h>
#include <stdlib.h>
#define MAX 20
struct Node {
int vertex;
struct Node* next;
};
struct Graph {
int V;
struct Node** adj;
};
int visited[MAX], queue[MAX];
int front = -1, rear = -1;
struct Node* createNode(int v) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}
struct Graph* createGraph(int V) {
int i;
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;
graph->adj = (struct Node**)malloc(V * sizeof(struct Node*));
for (i = 0; i < V; i++)
graph->adj[i] = NULL;
return graph;
}
void addEdge(struct Graph* graph, int src, int dest) {
struct Node* newNode = createNode(dest);
newNode->next = graph->adj[src];
graph->adj[src] = newNode;
newNode = createNode(src);
newNode->next = graph->adj[dest];
graph->adj[dest] = newNode;
}
void enqueue(int value) {
if (rear == MAX - 1)
return;
if (front == -1)
front = 0;
rear++;
queue[rear] = value;
}
int dequeue() {
int item;
if (front == -1 || front > rear)
return -1;
item = queue[front];
front++;
return item;
}
void BFS(struct Graph* graph, int start) {
int i, current;
struct Node* temp;
for (i = 0; i < graph->V; i++)
visited[i] = 0;
enqueue(start);
visited[start] = 1;
printf("\nBFS Traversal: ");
while (front <= rear) {
current = dequeue();
printf("%d ", current);
temp = graph->adj[current];
while (temp) {
int adjVertex = temp->vertex;
if (visited[adjVertex] == 0) {
enqueue(adjVertex);
visited[adjVertex] = 1;
}
temp = temp->next;
}
}
}
int main() {
int V, E, i, src, dest, start;
struct Graph* graph;
clrscr();
printf("Enter number of vertices: ");
scanf("%d", &V);
graph = createGraph(V);
printf("Enter number of edges: ");
scanf("%d", &E);
printf("Enter edges (source destination):\n");
for (i = 0; i < E; i++) {
scanf("%d %d", &src, &dest);
addEdge(graph, src, dest);
}
printf("Enter starting vertex for BFS: ");
scanf("%d", &start);
BFS(graph, start);
getch();
return 0;
}