[Data Structure] DFS (깊이 우선 탐색)

DFS

- 깊이 우선 탐색

- 인접 행렬(순환/stack), 인접 리스트로 구현

- 어떤 노드를 방문했는지 검사를 무조건 해줘야 한다 (검사를 안해주면 무한 루프에 빠진다)

• 검사를 위한 배열 int visited[MAX_VERTEX] → dfs 시작할 때, 전부 FALSE로 초기화

- 인접 행렬 : O(n²) (정점 n개)

- 인접 리스트 : O(n+e) (정점 n개, 간선 e개)

 

 

인접 행렬로 구현한 DFS

1. 순환 : dfs_mat_recur(graph* g, int v)

1. 정점 v에서부터 dfs 시작 
2. v는 방문완료니까 visited배열에 TRUE 표시
3. v의 인접 정점 w에서 탐색 시작 -- (1)
4. matrix[v][w] == 1 (인접)이고, visited[w] == FALSE (방문 X)이면, 정점 w에서부터 다시 dfs 반복 -- (2)
5. 모든 정점이 visited TRUE될 때 까지 (1), (2) 반복

void dfs_mat_recur(graph* g, int v) {
	int w; // v = 정점, w = v의 인접 정점
	visited[v] = TRUE; // 방문 완료 표시
	printf("정점 %d -> ", v);
	for (w = 0; w < g->n; w++) {
		if (g->matrix[v][w] == 1 && visited[w] == FALSE)
			// w가 v의 인접 정점 && w를 아직 방문 X
			dfs_mat_recur(g, w);
			// w부터 다시 dfs 탐색 시작
	}
}

 

 

2. stack : dfs_mat_stack(graph* g, int v)

1. 정점 v에서부터 dfs 시작
2. 정점 v를 저장할 stack 생성
3. v를 stack에 push 
4. stack에서 pop시키고, pop된 정점(w)에서 탐색 시작 -- (1)
5. pop된 정점(w)를 방문 완료로 표시 -- (2)
6. w의 인접 정점(k)들 모두 stack에 push -- (3)
7. → push 조건 : matrix[w][k] == 1 && visited[k] == FALSE && stack에 k존재 X
8. stack이 empty될 때까지 (1), (2), (3) 반복

int bool_stack(stack* s, element v) {
	// stack에 정점 v가 존재하는지 여부 확인
	int flag = 0;
	for (int i = 0; i <= s->top; i++) {
		if (s->stack[i] == v)
			flag = 1;
	}
	if (flag == 1) return TRUE;
	else return FALSE;
}

void dfs_mat_stack(graph* g, int v) {
	stack* s;
	s = createS(); init_stack(s);

	push(s, v);
	while (!is_empty(s)) {
		int w = pop(s);
		int k; // w의 인접 정점
		visited[w] = TRUE;
		printf("정점 %d -> ", w);
		for (k = 0; k < g->n; k++) {
			if (g->matrix[w][k] == 1 && visited[k] == FALSE && bool_stack(s, k) == FALSE) {
				push(s, k);
			}
		}
	}
	free(s);
}

 

 

 

인접 리스트로 구현한 DFS

1. 순환 :  dfs_list_recur(graph* g, int v)

1. 정점 v에서부터 dfs 시작
2. v는 방문완료니까 visited배열에 TRUE 표시
3. list[v]의 인접 graphnode의 정점(w->vertex)에서 탐색 시작 -- (1)
4. visited[w->vertex] == FALSE (방문 X)이면, list[w]에서부터 다시 dfs 반복 -- (2)
5. 모든 정점이 visited TRUE될 때 까지 (1), (2) 반복

void dfs_list_recur(graph* g, int v) {
	graphnode* w; // v의 인접 정점
	visited[v] = TRUE;
	printf("정점 %d -> ", v);
	for (w = g->list[v]; w; w = w->link) {
		if (visited[w->vertex] == FALSE)
			dfs_list_recur(g, w->vertex);
	}
}

 

 

2. stack : dfs_list_stack(graph* g, int v)

1. 정점 v에서부터 dfs 시작
2. 정점 v를 저장할 stack 생성
3. v를 stack에 push 
4. stack에서 pop시키고, pop된 정점(w)에서 탐색 시작 -- (1)
5. pop된 정점(w)를 방문 완료로 표시 -- (2)
6. list[w]의 인접 graphnode의 정점(k->vertex)들 모두 stack에 push -- (3)
7. → push 조건 : visited[k->vertex] == FALSE && stack에 k->vertex존재 X
8. stack이 empty될 때까지 (1), (2), (3) 반복

int bool_stack(stack* s, element v) {
	// stack에 정점 v가 존재하는지 여부 확인
	int flag = 0;
	for (int i = 0; i <= s->top; i++) {
		if (s->stack[i] == v)
			flag = 1;
	}
	if (flag == 1) return TRUE;
	else return FALSE;
}

void dfs_list_stack(graph* g, int v) {
	stack* s;
	s = createS(); init_stack(s);
	
	push(s, v);
	while (!is_empty(s)) {
		int w = pop(s);
		visited[w] = TRUE;
		graphnode* k; // w의 인접 정점
		printf("정점 %d -> ", w);
		for (k = g->list[w]; k; k = k->link) {
			if (visited[k->vertex] == FALSE && bool_stack(s, k->vertex) == FALSE)
				push(s, k->vertex);
		}
	}
	free(s);
}