Solution:
#include <stdio.h>
#include <stdlib.h>
#define SIZE 40
int n;
struct queue {
int items[SIZE];
int front;
int rear;
};
struct queue* createQueue();
void enqueue(struct queue* q, int);
int dequeue(struct queue* q);
void display(struct queue* q);
int isEmpty(struct queue* q);
void printQueue(struct queue* q);
struct node {
int vertex;
struct node* next;
};
struct node* createNode(int);
struct Graph {
int numVertices;
struct node** adjLists;
int* visited;
};
// BFS algorithm
void bfs(struct Graph* graph, int startVertex) {
struct queue* q = createQueue();
graph->visited[startVertex] = 1;
enqueue(q, startVertex);
while (!isEmpty(q)) {
printQueue(q);
int currentVertex = dequeue(q);
printf("\nVisited %d\n", currentVertex);
struct node* temp = graph->adjLists[currentVertex];
while (temp) {
int adjVertex = temp->vertex;
if (graph->visited[adjVertex] == 0) {
graph->visited[adjVertex] = 1;
enqueue(q, adjVertex);
}
temp = temp->next;
}
}
}
// Creating a node
struct node* createNode(int v) {
struct node* newNode = malloc(sizeof(struct node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}
// Creating a graph
struct Graph* createGraph(int vertices) {
struct Graph* graph = malloc(sizeof(struct Graph));
graph->numVertices = vertices;
graph->adjLists = malloc(vertices * sizeof(struct node*));
graph->visited = malloc(vertices * sizeof(int));
int i;
for (i = 0; i < vertices; i++) {
graph->adjLists[i] = NULL;
graph->visited[i] = 0;
}
return graph;
}
void addEdge(struct Graph* graph,int graph_type)
{
int i,max_edges,u,v;
if(graph_type==1)
{
max_edges = n*(n-1)/2;
}
else
{
max_edges = n*(n-1);
}
for(i=1;i<=max_edges;i++)
{
printf("Enter edge [%d] (-1 -1 to quit): ",i);
scanf("%d%d",&u,&v);
if((u==-1)&&(v==-1))
{
break;
}
else if(u>=n || v>=n || u<0 || v<0)
{
printf("Invalid vertex\n");
i--;
}
else
{
// Add edge from s to d
struct node* newNode = createNode(v);
newNode->next = graph->adjLists[u];
graph->adjLists[u] = newNode;
if(graph_type==1)
{ // Add edge from d to s
newNode = createNode(u);
newNode->next = graph->adjLists[v];
graph->adjLists[v] = newNode;
}
}
}
}
// Create a queue
struct queue* createQueue() {
struct queue* q = malloc(sizeof(struct queue));
q->front = -1;
q->rear = -1;
return q;
}
// Check if the queue is empty
int isEmpty(struct queue* q) {
if (q->rear == -1)
return 1;
else
return 0;
}
// Adding elements into queue
void enqueue(struct queue* q, int value) {
if (q->rear == SIZE - 1)
printf("\nQueue is Full!!");
else {
if (q->front == -1)
q->front = 0;
q->rear++;
q->items[q->rear] = value;
}
}
// Removing elements from queue
int dequeue(struct queue* q) {
int item;
if (isEmpty(q)) {
printf("Queue is empty");
item = -1;
} else {
item = q->items[q->front];
q->front++;
if (q->front > q->rear) {
printf("\nResetting queue ");
q->front = q->rear = -1;
}
}
return item;
}
// Print the queue
void printQueue(struct queue* q) {
int i = q->front;
if (isEmpty(q)) {
printf("Queue is empty");
} else {
printf("\nQueue contains \n");
for (i = q->front; i < q->rear + 1; i++) {
printf("%d ", q->items[i]);
}
}
}
int main()
{
int graph_type;
printf("\nEnter 1 for Undirected graph\nEnter 2 for Directed graph\n");
printf("\nEnter your choice :: ");
scanf("%d",&graph_type);
printf("Enter number of vertices :\n");
scanf("%d",&n);
struct Graph* graph = createGraph(n);
addEdge(graph,graph_type);
bfs(graph, 0);
return 0;
}
0 Comments