Algorithm:-
It work on stack.
Step 1. Initialize all the vertex to the Ready state.
Step 2. PUSH the starting vertex onto stack and change it's status to the working state.
Step 3. Repeat Step 4 and Step 5 until stack is empty.
Step 4. POP the Top vertex 'n' and process n and change it's status to the processed state.
Step 5. PUSH onto stack all the neighbours of the vertex 'n' . that are still in ready state and change their status to the waiting state.
Code:-
#include<stdio.h>
int stack[20];
int top=-1;
// FUNCTION FOR PUSH THE ELEMENT IN TO STACK
void push(int a)
{
top++;
stack[top]=a;
}
// function for pop the element fron the stack
int pop()
{
int a;
if(top==-1)
return 0;
else
{
a=stack[top];
top--;
return a;
}
}
int main()
{
int n,graph[10][10],visited[10]={0},i,j,flag=0,ans[10],k=0,a;
printf("Enter number of vertex in the graph\n");
scanf("%d",&n);
printf("Enter the graph in form of adjacency matrix\n");
for( i=1;i<=n;i++)
{
for( j=1;j<=n;j++)
scanf("%d",&graph[i][j]);
}
// logic for DFS
i=1;
while(i!=0)
{
if(visited[i]==0)
{
ans[k]=i;
k++;
}
visited[i]=1;
flag=0;
for( j=1;j<=n;j++)
{
if(visited[i]!=0)
{
if(graph[i][j]!=0)
{
flag=1;
// if vertex is not visited then push it into stack
if(visited[j]==0)
push(j);
}
}
}
// if there is no edge from vertex then
if(flag==0)
{
a=i;
while(1)
{
a++;
// if any edge from a to i then
if(graph[a][i]==1)
{
push(a);
break;
}
}
}
i=pop();
}
// printing the ans
printf("Traversal is:-\n");
for(i=0 ;i<k;i++)
printf("%d ",ans[i]);
return 0;
}
Output:-
Enter number of vertex in the graph
6
Enter the graph in form of adjacency matrix
0 0 0 0 0 0
1 0 0 1 0 0
0 1 0 0 0 1
0 0 1 0 1 1
1 0 0 0 0 0
0 1 0 0 1 0
Traversal is:-
1 2 4 6 5 3
 of the graph){kind=link}