깊이우선 탐색 (DFS)

안녕하세요 C++ 공부하고있는 대학생입니다.
이번에는 DFS에 대하여 정리하고자 합니다.
DFS에는 BFS처럼 몇가지 필수사항이 있습니다.

1. 연결되어있는 노드의 끝점까지 탐색한다.
2. 노드간 서로 연결되어있어야 하며, 2차원배열로 바라보면 연결되는걸 쉽게 파악 할 수 있다.
3. 자료구조 스택을 사용한다.
4. DFS문에서 재귀 혹은 루프문으로 해결한다.
   =>저는 재귀로 풀었습니다.

이렇게 4가지정도로 간략하게 볼 수 있습니다.

우선 그림으로 먼저 보여드리겠습니다.

그림과 같이 먼저 연결 한 다음에 DFS를 수행 할 예정입니다.

노드간의 연결은 전에 올렸던 BFS와 동일하게 코드를 만들었습니다.

	int number = 0;
	int start = 0;
	int one,two;
	printf("input number : ");
	scanf("%d",&number);
	printf("\n");
	int **map =(int **)malloc(sizeof(int) * number+1);
	for(int i =0; i<=number+1; i++) {
		map[i] = (int *)malloc(sizeof(int) * number);
	}
	int *visit = (int *)malloc(sizeof(int) * number+1);
	
	for(int i = 1; i<=number; i++) {
		printf("input data1 , data2 : ");
		scanf("%d %d",&one,&two);
		printf("\n");
		map[one][two] = map[two][one] = 1;
		visit[i] = 0;
		vertex++;
	}

map(노드연결)에 해당되는 2차원배열을 동적할당 하였고, visit(방문확인) 에 대한 1차원 배열을 동적할당 하였습니다.

그리고 두개의 값을 각각의 노드에 연결 해 주는 과정을 반복문을 통해 수행하였습니다.

다음으로 DFS 코드를 보여드리겠습니다.

void DFS(Tree *tree,Stack *stack,int **map,int *visit,int start) {
	if(tree->count!=0) {
		pop(tree);
	}
	else {
		visit[start] = 1;
		printf("%d ",start);
		push(tree,index,start);
	}
	start = backStack(tree);
	for(int i = start; i<=vertex; i++) {
		if(map[start][i] == 1 && visit[i] == 0) {
			visit[i] = 1;
			push(tree,index,i);
			start = backStack(tree);
			printf("%d ",i);
		}
	}

	if(tree->count == 0) return;
	else DFS(tree,stack,map,visit,start);
	
}

처음에 if 조건문을 통해 스택의 갯수가 0이 아니라면 pop 함수를 통해 stack에 있는 값을 반환 해 주도록 하였습니다.

else문은 처음 루트노드에 해당되는 부분에 대한 저장을 하는곳으로, visit[start] 라고 잡아두고 루트노드에 대해 방문했음을 표시하기위해 1값으로 치환하였습니다. 그런다음, 스택에 push 함수를 통해 넣어주었습니다.

이 조건문이 모두 끝나고, start라는 변수에 스택에 있는 front값을 가져오고,
for 반복문을 통해 연결되어있는 노드를 확인 후 , 연결되어있는 노드에 대해 방문했음을 표시 해 주고, 스택에 넣어주었습니다.

반복문이 끝난 후, 스택에 값이 모두 반환되었으면 return으로 void형 함수를 반환 해 주고, 아니라면 다시 DFS로 재귀형식으로 실행하였습니다.

과정을 정리 해 보겠습니다.

1. 루트노드 1을 스택에 넣는다.
2. 인접한 노드 2를 스택에 넣는다.
3. 인접한 노드 3을 스택에 넣는다.
4. 3에 인접한 6노드를 스택에 넣는다. 6에 인접한 노드가 없으므로 6을 반환한다.
5. 3에 인접한 7노드를 스택에 넣는다. 7역시 인접한 노드가 없으므로 7을 반환한다.
6. 3노드를 반환한다.
7. 4노드에 접근하고 스택에 넣는다.
8. 4에 인접한 8노드를 스택에 넣고 인접한 노드가 없으므로 반환한다.
9. 4를 반환하고, 2노드에 인접한 5노드에 접근한다.
10. 5노드에 인접한 9노드를 스택에 넣고 9노드 역시 인접한 노드가 없으므로 반환한다.
11. 5노드를 반환하고 2노드를 반화하고 1노드를 반환한다.

이렇게 과정이 나뉘어져있습니다.

스택은 연결리스트로 구현하였습니다.

typedef struct Stack {
	struct Stack* next;
	struct Stack* prev;
	int data;
}Stack;

typedef struct Tree {
	struct Stack* head;
	struct Stack* tail;
	int count;
}Tree;

Tree *init() {
	Tree* tree = (Tree *)malloc(sizeof(Tree));
	if(tree ==NULL) {
		printf("err\n");
	}
	else {
		tree->tail = NULL;
		tree->head = NULL;
		tree->count = 0;
		return tree;
	}
}

void push(Tree *tree,int index, int data) {
	Stack *stack = (Stack *)malloc(sizeof(Stack));
	Stack *preStack = tree->tail;
	stack->data = data;
	
	if(tree->count == 0) {
		stack->next = stack;
		stack->prev = stack;
		tree->tail = stack;
		tree->head = stack;
		tree->count++;
	}
	else {
		stack->next = preStack->next;
		stack->prev = preStack;
		preStack->next = stack;
		stack->next->prev = stack;
		
		if(tree->count == index) {
			tree->tail = stack;
		}
		tree->count++;
		index++;
	}
}

int backStack(Tree *tree) {
	Stack *curStack = tree->tail;
	return curStack->next->data;
}

void pop(Tree *tree) {
	Stack *curStack = tree->tail;
	Stack *preStack = tree->tail;
	
	if(tree->count == 0) {
		printf("err\n");
		return;
	}
	else {
		for(int i =0; i<tree->count; i++) {
			preStack = preStack->next;
		}
		curStack = preStack->next;
		preStack->next = curStack->next;
		curStack->next->prev = tree->tail;
		free(curStack);
		tree->count--;
		index--;
	}
}

void print(Tree *tree) {
	int i;
	Stack *curStack;
	if(tree->count == 0) {
		printf("none\n");
		return;
	}
	else {
		for(i = 0,curStack = tree->tail; i<tree->count; i++,curStack = curStack->prev) {
			printf("%d ",curStack->data);
		}
	}
}

실제로 print 함수는 이 코드에서 사용하지는 않지만, 체크용으로 따로만들어서 체크를 해 보면서 코드를 만들었습니다.

pop함수는 반환으로 해당 리스트를 delete를 해주고, free로 반환 해 줍니다.

backStack은 front에 해당되는 부분으로 LIFO 특성을 이용하여 마지막으로 들어간 리스트의 값을 반환함으로써 가져옵니다.

init은 tree 구조체에 대한 초기화 함수로, 한번의 동적할당으로 해당 구조체의 tail과 head 포인터형 구조체, count 변수를 사용하기 위해 사용하였습니다.

마지막으로 총 코드를 보여드리겠습니다.

#include <stdio.h>
#include <stdlib.h>

int index = 0;
int vertex = 0;

typedef struct Stack {
	struct Stack* next;
	struct Stack* prev;
	int data;
}Stack;

typedef struct Tree {
	struct Stack* head;
	struct Stack* tail;
	int count;
}Tree;

Tree *init() {
	Tree* tree = (Tree *)malloc(sizeof(Tree));
	if(tree ==NULL) {
		printf("err\n");
	}
	else {
		tree->tail = NULL;
		tree->head = NULL;
		tree->count = 0;
		return tree;
	}
}

void push(Tree *tree,int index, int data) {
	Stack *stack = (Stack *)malloc(sizeof(Stack));
	Stack *preStack = tree->tail;
	stack->data = data;
	
	if(tree->count == 0) {
		stack->next = stack;
		stack->prev = stack;
		tree->tail = stack;
		tree->head = stack;
		tree->count++;
	}
	else {
		stack->next = preStack->next;
		stack->prev = preStack;
		preStack->next = stack;
		stack->next->prev = stack;
		
		if(tree->count == index) {
			tree->tail = stack;
		}
		tree->count++;
		index++;
	}
}

int backStack(Tree *tree) {
	Stack *curStack = tree->tail;
	return curStack->next->data;
}

void pop(Tree *tree) {
	Stack *curStack = tree->tail;
	Stack *preStack = tree->tail;
	
	if(tree->count == 0) {
		printf("err\n");
		return;
	}
	else {
		for(int i =0; i<tree->count; i++) {
			preStack = preStack->next;
		}
		curStack = preStack->next;
		preStack->next = curStack->next;
		curStack->next->prev = tree->tail;
		free(curStack);
		tree->count--;
		index--;
	}
}

void print(Tree *tree) {
	int i;
	Stack *curStack;
	if(tree->count == 0) {
		printf("none\n");
		return;
	}
	else {
		for(i = 0,curStack = tree->tail; i<tree->count; i++,curStack = curStack->prev) {
			printf("%d ",curStack->data);
		}
	}
}

void DFS(Tree *tree,Stack *stack,int **map,int *visit,int start) {
	if(tree->count!=0) {
		pop(tree);
	}
	else {
		visit[start] = 1;
		printf("%d ",start);
		push(tree,index,start);
	}
	printf("stack : ");
	print(tree);
	printf("\n");
	start = backStack(tree);
	for(int i = start; i<=vertex; i++) {
		if(map[start][i] == 1 && visit[i] == 0) {
			visit[i] = 1;
			push(tree,index,i);
			start = backStack(tree);
			printf("%d ",i);
		}
	}

	if(tree->count == 0) return;
	else DFS(tree,stack,map,visit,start);
	
}

int main() {
	Tree *tree = init();
	Stack *stack;
	int number = 0;
	int start = 0;
	int one,two;
	printf("input number : ");
	scanf("%d",&number);
	printf("\n");
	int **map =(int **)malloc(sizeof(int) * number+1);
	for(int i =0; i<=number+1; i++) {
		map[i] = (int *)malloc(sizeof(int) * number);
	}
	int *visit = (int *)malloc(sizeof(int) * number+1);
	
	for(int i = 1; i<=number; i++) {
		printf("input data1 , data2 : ");
		scanf("%d %d",&one,&two);
		printf("\n");
		map[one][two] = map[two][one] = 1;
		visit[i] = 0;
		vertex++;
	}
	printf("input start : ");
	scanf("%d",&start);
	printf("\n");
	
	DFS(tree,stack,map,visit,start);
	
	return 0;
}

DFS는 BFS와 비슷하지만 돌아가는 원리가 조금 다른점에 있어서 책이랑 블로그를 통해서 공부하고, 블로그에 좋은 예시그림이 그 그림을 데이터로 넣어서 제 소스코드에 돌렸을 때 데이터가 잘 출력되는지 확인 해 보았습니다.
결과를 보여드리겠습니다.

아까 과정대로,
1 -> 2 -> 3 -> 6 -> 7 ->4 -> 8 -> 5 -> 9 순서대로 깊이우선검색을 한 것을 볼 수 있습니다.