Pages - Menu

Thursday, 23 May 2019

Implementation of Breadth First Search BFS in C

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