Here is the code
#include<stdio.h>
#include<stdlib.h>
struct node {
int data;
struct node *next;
};
struct node *front=NULL, *rear=NULL;
struct node *nodeList[20];
void bfs(int*);
void insert(int, int);
void addQueue(int);
int getQueue();
struct node* getNode(int);
void main() {
int numberOfVertices,numberOfEdges, i, j, v1, v2, visited[20];
printf("Enter the number of vertices\n");
scanf("%d", &numberOfVertices);
for (i=0;i<=numberOfVertices;i++) {
visited[i] = 0;
nodeList[i]=NULL;
}
printf("Enter the number of edges\n");
scanf("%d", &numberOfEdges);
for (i=0;i<numberOfEdges;i++) {
printf("Enter the edges\n");
scanf("%d %d", &v1, &v2);
insert(v1, v2);
}
addQueue(1); // insert start node in queue
bfs(visited);
}
// vertax is v1 and it points to v2 so add v2 in linked list of node v1
// add v2 to nodeList[v1]
void insert(int v1, int v2) {
struct node *temp2;
struct node *temp = getNode(v2);
if (nodeList[v1]==NULL) {
nodeList[v1] = temp;
} else {
temp2 = nodeList[v1];
while(temp2->next != NULL) {
temp2 = temp2->next;
}
temp2->next = temp;
}
}
void bfs(int *visited) {
struct node *temp;
int vertex = getQueue();
if (vertex == -1) {
return;
}
if (visited[vertex] != 1) {
printf("%d\t", vertex);
visited[vertex] = 1;
temp = nodeList[vertex];
while (temp != NULL) {
if (visited[temp->data] != 1) {
addQueue(temp->data);
}
temp = temp -> next;
}
}
bfs(visited);
}
void addQueue(int data) {
struct node *temp;
if (front == NULL) {
rear = front = getNode(data);
} else {
rear -> next = getNode(data);
rear = rear -> next;
}
}
int getQueue() {
int temp;
if (front == NULL) {
return -1;
}
if (front == rear) {
temp = front -> data;
free(front);
front = rear = NULL;
return temp;
} else {
temp = front -> data;
front = front -> next;
return temp;
}
}
struct node* getNode(int data) {
struct node *temp = (struct node*)malloc(sizeof(struct node));
temp->data = data;
temp->next = NULL;
return temp;
}
No comments:
Post a Comment