1. 깊이 우선 탐색 방법 (Depth First Search, DFS)
ㅇ 방법 요약
- 갈 수 있는데까지 가보다가, 더이상 진행 못하면 거슬러 올라와서(되돌아와서),
. 즉, 최대한 멀리 (깊숙히) 있는 노드를 우선으로 탐색하는 방식을 취함
- 되돌아온 갈림길에서, 미방문 노드가 있으면, 또다시 갈 수 있는데까지 가서 탐색하는 방법
ㅇ 구현 방법 : 주로, `스택 반복` 또는 `재귀 반복`으로 구현
ㅇ 시간 복잡도 : 선형 시간
- O(N + M) : 각 정점을 1번씩 만 방문하고, 각 간선을 1번씩 만 지나감
. 여기서, N은 정점의 수, M은 간선의 수
2. 알고리즘 구현 例) (스택 반복 구현)
ㅇ 구현 개요
- 매 정점 마다, 인접 정점들 중 미방문 정점들을 스택에 추가하고,
- 방문할 정점을 탐색할 때, 스택에서 하나씩 꺼냄
ㅇ 구현 특징
- 자료구조 : 후입선출(LIFO)인 `스택` 자료구조를 활용
- 입력 : 특정 그래프(G), 시작 정점(v)
. 여기서, G는 인접 리스트에 의한 그래프 표현으로 가정 함
- 출력 : 방문한 정점들이 열거된, 크기가 |V|인, 배열 또는 리스트 (visited)
. visited[i]가, true이면 이미 방문, false 이면, 미 방문
stackDFS(G, v)
stack = createStack() ①
visited = createArray(|V|) ②
for (i=0; i<|V|; i++) ③
visited[i] = FALSE
push(stack, v) ④
while (not isEmpty(stack)) ⑤
c = pop(stack) ⑥
visited[c] = TURE ⑦
for i in adjacencyList(G, c) ⑧
if not visited[i] ⑨
push(stack, i)
return visited; ⑩
ㅇ 구현 단계
- ① 스택 자료구조의 생성 (미방문 정점들로써, 빈 스택)
- ② 방문 여부를 기록하게될 정점들의 배열(또는,리스트)의 생성 (빈 배열)
- ③ 방문 정점 배열에 대한 초기화 (전체 미방문으로 false 설정)
- ④ 시작 정점을 빈 스택에 추가
- ⑤ 미방문 정점들을 들어있는 스택이 빌 때까지 반복
- ⑥ 방문할 정점을 스택에서 꺼냄
- ⑦ 현재 방문 정점에 방문했음(true)을 기록
- ⑧ 인접리스트에 의한 그래프 표현(G)으로부터, 인접 정점들을 추출하고, 차례대로 탐색
- ⑨ 이들 중에 해당 정점이,
. 미방문이면, 방문할 정점이므로, 미방문 스택에 이를 추가하고, ⑤ 반복
. 방문이면, 그냥 ⑤ 반복
- ⑩ 방문 여부 기록된 배열(visited)을 반환
3. 알고리즘 구현 例) (재귀 반복 구현)
ㅇ 구현 특징
- 입력 : 특정 그래프(G), 시작 정점(v)
. 여기서, G는 인접 리스트에 의한 그래프 표현으로 가정 함
- 외부 데이터 : 알고리즘이 접근하여, 읽고 수정 가능한 배열 (visited)
. 알고리즘 동작 이전에, 정점 수 |V| 크기로, 초기화된 visited 배열을, 생성할 필요 있음
. visited[i]가, true이면 이미 방문, false 이면, 미 방문
recursiveDFS(G, v)
visited[v] = TRUE ①
for i in adjacencyList(G, v) ②
if not visited[i] ③
recursiveDFS(G, i) ④
ㅇ 구현 단계
- ① 입력(v)으로 주어진, 현재 방문 정점에 방문했음(true)을 기록
- ② 인접리스트에 의한 그래프 표현(G)으로부터,
. 현재 방문 정점의 인접 정점들을 추출하고, 이들을 차례대로 탐색
- ③ 만일 해당 정점이 미방문이면,
- ④ 재귀 반복(recursiveDFS)