Thursday, 28 December 2017

Write C programs for implementing the following graph Depth-first traversal algorithms:

A) DFS(depth-first search) Algorithm 

Globally declare
int stack[20],top=-1,a[20][20],vis[20];
int pop();
void push(int item);

1. Algorithm : 
void dfs(int s,int n)
Step1: Declare integer variable i,k
Step2: call subfunction push(s)
Step3: Assign vis[s]=1
Step4: call subfunction k=pop()
Step5: check k notequal to 0
if(k!=0)
Step6: Print k
Step7: Repeat while(k!=0) upto Step: 14
Step8: Repeat for(i=1;i<=n;i++) upto Step: 14
Step9: Check upto Step: 11 if((a[k][i]!=0)&&(vis[i]==0))
Step10: call subfunction push(i);
Step11: vis[i]=1;
Step12: Assign k=pop();
Step13: Check if(k!=0)
Step14: print k
Step15: Repeat for(i=1;i<=n;i++)
Step16: Check if(vis[i]==0)
Step17: call subfunction dfs(i,n);
Step:18 Stop

2. Algorithm : 
void push(int item)
Step1: Start
Step2: Check top equal to 19
if(top==19)
Step3: print Stack overflow
Step4: otherwise stack[++top]=item;
Step5: stop

3. Algorithm : 
int pop()
Step1: Start
Step2: Declare int k;
Step3: check top equal to -1
if(top==-1) return(0);
Step4: otherwise check upto 6
Step5:k=stack[top--];
Step6: return(k);
Step7: stop

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