Algorithm
1 procedure DFS(G,v):
2 label v as explored
3 for all edges e in G.incidentEdges(v) do
4 if edge e is unexplored then
5 w ← G.opposite(v,e)
6 if vertex w is unexplored then
7 label e as a discovery edge
8 recursively call DFS(G,w)
9 else
10 label e as a back edge
Program
#include<stdio.h>
#include<conio.h>
#define MAX 5
int dfs(int adj[][MAX],int visited[],int start)
{
int stack[MAX];
int top=-1,i;
printf("%c-",start+65);
visited[start]=1;
stack[++top]=start;
while(top!=-1)
{
start=stack[top];
for(i=0;i<MAX;i++)
{ if(adj[start][i]&&visited[i]==0)
{stack[++top]=i;
printf("%c-",i+65);
visited[i]=1;
break;
}}
if(i==MAX)
top--;
}
return 0;
}
int main()
{
int adj[MAX][MAX]={{0,0,1,1,0},{0,0,0,0,0},{0,1,0,1,1},{0,0,0,0,1},{0,0,0,1,0}};
int visited[MAX]={0};
printf("DFS Traversal : ");
dfs(adj,visited,0);
printf("\n");
getch();
return 0;
}
1 procedure DFS(G,v):
2 label v as explored
3 for all edges e in G.incidentEdges(v) do
4 if edge e is unexplored then
5 w ← G.opposite(v,e)
6 if vertex w is unexplored then
7 label e as a discovery edge
8 recursively call DFS(G,w)
9 else
10 label e as a back edge
Program
#include<stdio.h>
#include<conio.h>
#define MAX 5
int dfs(int adj[][MAX],int visited[],int start)
{
int stack[MAX];
int top=-1,i;
printf("%c-",start+65);
visited[start]=1;
stack[++top]=start;
while(top!=-1)
{
start=stack[top];
for(i=0;i<MAX;i++)
{ if(adj[start][i]&&visited[i]==0)
{stack[++top]=i;
printf("%c-",i+65);
visited[i]=1;
break;
}}
if(i==MAX)
top--;
}
return 0;
}
int main()
{
int adj[MAX][MAX]={{0,0,1,1,0},{0,0,0,0,0},{0,1,0,1,1},{0,0,0,0,1},{0,0,0,1,0}};
int visited[MAX]={0};
printf("DFS Traversal : ");
dfs(adj,visited,0);
printf("\n");
getch();
return 0;
}