Thursday, June 16, 2011

Algorithm and Program for Depth First Search(DFS)

Algorithm
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;
}