[go: up one dir, main page]
Scribd
Upload
62 views3 pages

Program To Implement Breadth-First-Search (BFS)

This document implements breadth-first search (BFS) on a graph data structure represented by an adjacency list. It initializes color, distance, and predecessor arrays, enqueues the starting node, and repeatedly dequeues nodes to explore their unvisited neighbors, updating the arrays and enqueueing neighbors. The distances and predecessors of all reached nodes from the source are then printed.

Uploaded by

Shubham Jain
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
62 views3 pages

Program To Implement Breadth-First-Search (BFS)

This document implements breadth-first search (BFS) on a graph data structure represented by an adjacency list. It initializes color, distance, and predecessor arrays, enqueues the starting node, and repeatedly dequeues nodes to explore their unvisited neighbors, updating the arrays and enqueueing neighbors. The distances and predecessors of all reached nodes from the source are then printed.

Uploaded by

Shubham Jain
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
You are on page 1/ 3

// Program to implement Breadth-First-Search (BFS)

#include<stdio.h> #include<conio.h> #include<stdlib.h> #define MAX 100 void bfs(int n,int s); void enqueue(int q[],int m); int dequeue(int q[]); int color[MAX]; int d[MAX]; int pi[MAX]; typedef struct vert* ver; struct vert { int ident; ver next; } cor; ver adj_list[MAX]; void main() { int n,i,j,k,s,u; ver temp,prev; clrscr(); printf("Enter no of nodes : "); scanf("%d",&n); for(i=0;i<=n;i++) adj_list[i]='\0'; for(i=1;i<=n;i++) { prev=NULL; printf("Enter No of vertex connected to %d :",i); scanf("%d",&j); for(k=0;k<j;k++) { temp=(ver)malloc(sizeof(cor)); temp->next=NULL; printf("Enter Vertex No. connected to vertex %d : ",i); scanf("%d",&temp->ident); if(prev==NULL) adj_list[i]=temp; else

prev->next=temp; prev=temp; } } printf("\nEnter the starting point of graph : "); scanf("%d",&s); bfs(n,s); for(i=1;i<=n;i++) { printf("\nThe Distance from source(%d) to %d is %d",s,i,d[i]); printf("\nThe previous vertex of %d is %d",i,pi[i]); } getch(); } void bfs(int n,int s) { int i,v,q[MAX],u; ver temp; for(i=1;i<=n;i++) { if(i==s) continue; color[i]=0; d[i]=32767; pi[i]=NULL; } color[s]=1; d[s]=0; pi[s]=NULL; for(i=0;i<=n;i++) q[i]='\0'; enqueue(q,s); while(q[0]!='\0') { u=dequeue(q); temp=adj_list[u]; while(temp!=NULL) { v=temp->ident; if(color[v]==0) { color[v]=1; d[v]=d[u]+1; pi[v]=u; enqueue(q,v); }

temp=temp->next; } color[u]=2; } } void enqueue(int q[MAX],int m) { int i=0; while(q[i]!='\0') { i++; } q[i]=m; } int dequeue(int q[MAX]) { int i=0,ret; ret=q[i]; while(q[i]!='\0') { q[i]=q[i+1]; i++; } return ret; }

You might also like