Depth First Search(DFS)

Aim: To implement Depth First Search non recursively

Program:

#include<stdio.h>

#include<conio.h>

int n,am[10][10],stk[10],st,v,i,j,visited[10],top=0;

void main()

{

clrscr();

printf("enter number of vertices");

scanf("%d",&n);

printf("enter adjacent matrix");

for(i=1;i<=n;i++)

{

for(j=1;j<=n;j++)

scanf("%d",&am[i][j]);

visited[i]=0;

}

printf("enter source node:");

scanf("%d",&st);

dfs(st);

getch();

}

dfs(int st)

{

top++;

stk[top]=st;

while(top>0)

{

v=stk[top];

top--;

if(visited[v]==0)

{

visited[v]=1;

printf("-->%d",v);

}

for(i=n;i>=1;i--)

{

if(am[v][i]==1 && visited[i]==0)

{

if(instack(i)==0)

{

top++;

stk[top]=i;

}

}

}

}

}

int instack(int n)

{

for(j=1;j<=top;j++)

{rix

if(stk[j]==n)

return 1;

}

return 0;

}

Input:

   The input is given in adjacency matrix as given below graph

Output: