#include<stdio.h>

#define MAX 5

//depth-first search, non-recursive version
int dfs(int adj[][MAX],int visited[],int start)
{
  int stack[MAX];
  int i, top = -1;
    
  printf("%c-", start+'1');
  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+'1');
        visited[i] = 1;
        break;
      }
    }  

    if(i == MAX)
      top--;
  }
  return 0;
}

int getUnmarkedNode(int visited[])
{
  int j = 0;
  while (visited[j] == 1 && j < MAX)
    ++j;
  return j;
}


//depth-first search, recursive variant
int dfs_rec(int adj[][MAX],int visited[],int start)
{
  int i;

  printf("%c-", start+'1');
  visited[start] = 1;
  for(i=0;i<MAX;i++)
  {
      if(adj[start][i] && visited[i] == 0)
      {
        dfs_rec(adj,visited,i);
      }
  }

  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 adj[MAX][MAX] = {{0,1,1,0,0},{0,0,0,1,0},{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0}};
//  int adj[MAX][MAX] = {{0,1,1,0,0},{0,0,0,0,0},{0,0,0,0,0},{0,1,0,0,0},{0,0,0,0,0}};
  int visited[MAX] = {0};
  int j = 0;

  printf("DFS Traversal : ");

  while ((j = getUnmarkedNode(visited)) != MAX)
    dfs_rec(adj,visited,j);
  printf("\n");

  return 0;
}