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

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

728x90

DFS

깊이 우선 탐색

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

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

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

→ dfs 시작할 때, 전부 FALSE로 초기화 인접 행렬 : O(n²) (정점 n개)

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

인접 행렬(순환) dfs_mat_recur(graph* g, int v)

정점 v에서부터 dfs 시작

v는 방문완료니까 visited배열에 TRUE 표시

표시 v의 인접 정점 w 에서 탐색 시작 -- (1)

에서 탐색 시작 -- (1) matrix[v][w] == 1 (인접) 이고, visited[w] == FALSE (방문 X) 이면, 정점 w에서부터 다시 dfs 반복 -- (2)

이고, 이면, 정점 w에서부터 다시 dfs 반복 -- (2) 모든 정점이 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 탐색 시작 } }

인접 행렬(stack) dfs_mat_stack(graph* g, int v)

정점 v에서부터 dfs 시작

정점 v를 저장할 stack 생성

v를 stack에 push

stack에서 pop시키고, pop된 정점(w)에서 탐색 시작 -- (1)

pop된 정점(w)를 방문 완료로 표시 -- (2)

w의 인접 정점(k)들 모두 stack에 push -- (3)

→ push 조건 : matrix[w][k] == 1 && visited[k] == FALSE && stack에 k존재 X

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_list_recur(graph* g, int v)

정점 v에서부터 dfs 시작

v는 방문완료니까 visited배열에 TRUE 표시

표시 list[v]의 인접 graphnode의 정점(w->vertex) 에서 탐색 시작 -- (1)

에서 탐색 시작 -- (1) visited[w->vertex] == FALSE (방문 X) 이면, list[w]에서부터 다시 dfs 반복 -- (2)

이면, list[w]에서부터 다시 dfs 반복 -- (2) 모든 정점이 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); } }

인접 리스트(stack) dfs_list_stack(graph* g, int v)

정점 v에서부터 dfs 시작

정점 v를 저장할 stack 생성

v를 stack에 push

stack에서 pop시키고, pop된 정점(w)에서 탐색 시작 -- (1)

-- (1) pop된 정점(w)를 방문 완료로 표시 -- (2)

list[w]의 인접 graphnode의 정점(k->vertex) 들 모두 stack에 push -- (3)

들 -- (3) → push 조건 : visited[k->vertex] == FALSE && stack에 k->vertex존재 X

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

728x90

반응형

from http://cs-ssupport.tistory.com/207 by ccl(A) rewrite - 2021-12-23 23:26:38