DFS Traversal Algorithm C source

#include <stdio.h>
#include <time.h>

#define STACK_SIZE 10

int push(int* stack, int* top, int value);
int pop(int* stack, int *top, int *value);
int Dfs(int (*dfs)[11], int* pred, int* r_stack, int* r_top);

main()
{
int i,j, k;
int temp;
int dfs_array[10][11]={
{0, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1},
{0, 2, 3, 7, 9, -1, -1, -1, -1, -1, -1},
{0, 1, 4, 8, -1, -1, -1, -1, -1, -1, -1},
{0, 1, 4, 5, -1, -1, -1, -1, -1, -1, -1},
{0, 2, 3, -1, -1, -1, -1, -1, -1, -1, -1},
{0, 3, 6, -1, -1, -1, -1, -1, -1, -1, -1},
{0, 5, 7, -1, -1, -1, -1, -1, -1, -1, -1},
{0, 1, 6, -1, -1, -1, -1, -1, -1, -1, -1},
{0, 0, 2, 9, -1, -1, -1, -1, -1, -1, -1},
{0, 1, 8, -1, -1, -1, -1, -1, -1, -1, -1}
};

int r_stack[10];
int r_top = 0;

int pred[10];
double start, finish;

start = clock();

printf("BFS 알고리즘\n");

Dfs(dfs_array, pred, r_stack, &r_top);

printf("Pred : ");
for(i=0; i<9; i++)
{
printf("%d ", pred[i]);
}
printf("\n");

printf("Stack : ");
for(i=0; i<9; i++)
{
printf("%d ", r_stack[i]);
}
printf("\n");

finish =clock();
printf("소요시간 : %f\n",(finish-start) / (double)CLOCKS_PER_SEC );

}

int Dfs(int (*dfs)[11], int* pred, int* r_stack, int* r_top)
{
int i,j;

int k=1;//vertex가 가리키는값의 위치
int source;//시작점

int s_stack[10];
int s_top = 0;

int pointer = 0;//현재 vertex의 위치
int temp;

printf("source vertex를 선택하세요 : ");
scanf("%d", &source);

pred[source] = -1;//pred 시작점 표시
dfs[source][0] = 1;//true false 구분

push(s_stack, &s_top, source);
push(r_stack, r_top, source);

if(dfs[source][1] > 0)// source가 가르키는값이 존재할때
{
pointer = dfs[source][1];//다음 vertex는 source가 가르키는값
pred[pointer] = source;//다음 vertex의 pred는 source
}

else
return 1;

while(1)
{
//if(dfs[pointer][0] == 0)//현재 vertex가 미 방문일때
{
if(s_top<=0)
return 0;

if(k==1 && (dfs[pointer][0] == 0))//
{
dfs[pointer][0] = 1;//true false 구분

push(s_stack, &s_top, pointer);
push(r_stack, r_top, pointer);
}

temp = dfs[pointer][k];
if(dfs[pointer][k] >= 0 && (dfs[temp][0] == 0))
{//현재 vertex가 가르키는값이 존재하고 미 방문일때

temp = pointer;
pointer = dfs[pointer][k];//가르키는 값이 다음 지시자
pred[pointer] = temp;//pred는 기존 지시자 삽입

k=0;
}

else if(dfs[pointer][k] < 0)//vertex가 가르키는 값이 모두 방문일때
{
pop(s_stack, &s_top, &temp);
//pop(s_stack, &s_top, &temp);
pointer = s_stack[s_top];
k=0;
}

k++;//vertex가 가르키는 값이 이미 방문일때 다음값 지정
}
}
}

int push(int* stack, int* top, int value)
{

if(*top >= STACK_SIZE)
{
printf("input's size is over the range \n");
return 1;
}

stack[*top] = value;
(*top)++;

return 0;
}

int pop(int* stack, int *top, int *value)
{
if(*top < 0)
{
printf("no more data in stack \n");
return 1;
}

(*top)--;
*value = stack[*top];

return 0;
}

dfs.c