Thursday, 28 December 2017

Write C programs for implementing the following graph breadth-first search traversal algorithms.

BFS(breadth-first search) Algorithm:

Globally declare
int q[20],top=-1,front=-1,rear=-1,a[20][20],vis[20];
int delete();
void add(int item);

1. Algorithm: 
void bfs(int s,int n)
Step1:Start
Step2: Declare int p,i;
Step3: call subfunction add(s);
Step4: assign vis[s]=1;
Step5: call subfunction p=delete();
Step6: Check if(p!=0)
Step7: print p
Step8: Repeat while(p!=0)
Step9: Repeat for(i=1;i<=n;i++)
Step10: Check if((a[p][i]!=0)&&(vis[i]==0))
Step11: call subfunction add(i);
Step12: assign vis[i]=1;
Step13: call subfunction p=delete();
Step14: Check if(p!=0)
Step15: print p
Step16: Repeat for(i=1;i<=n;i++)
Step17: if(vis[i]==0)
Step18: call subfunction bfs(i,n);
Step19: Stop

2. Algorithm: 
void add(int item)
Step1: Start
Step2: if(rear==19)
Step3: print QUEUE FULL
Step4: else
Step5: if(rear==-1)
Step6: q[++rear]=item;
Step7: front++;
Step8: otherwise else
Step9: q[++rear]=item;
Step10: Stop

3. Algorithm: 
int delete()
Step1: Start
Step2: Declare int k;
Step3: Check if((front>rear)||(front==-1))
return(0);
Step4: otherwise
Step5: k=q[front++];
Step6: return(k);

4. Algorithm: 
int main()
Step1: Start
Step2: Declare int n,i,s,j;
Step3: Read the number vertices's n
Step4: Read 1 if has a node else 0 i,j
Step5: Print The ADJACENCY MATRIX IS a[i][j]
Step6: Repeat for(i=1;i<=n;i++)
Step7: Assign vis[i]=0;
Step8: Read the source vertex s
Step: call sub function bfs(s,n);
Step:Stop


Thanks
Mukesh Rajput

No comments:

Post a Comment

Thanks
Mukesh Rajput