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