728x90
반응형
깊이 우선 탐색(Depth First Search, DFS)
: 하나의 정점으로부터 시작하여 깊은 곳 우선으로 탐색하여 최종적으로 연결된 모든 정점을 탐색하는 방법
특징
① 경로상의 노드들만 기억하면 되므로 차지하는 저장 공간이 적다.
② 같은 레벨의 경로보다 더 깊은 레벨을 우선으로 탐색한다.
③ 재귀적으로 동작하며, 후입 선출(LIFO, Last In First Out) 구조이다.
알고리즘
① 시작 정점 v를 결정하여 방문
② 정점 v에 인접한 정점 중
1. 방문하지 않은 정점 w가 있으면, 정점 v를 스택에 push 하고 w를 방문하고 w를 v에 대입하여 ②과정 반복 수행
2. 방문하지 않은 정점이 없으면, 탐색의 방향을 바꾸기 위해 마지막 방문 정점을 스택을 pop 하여 받은 정점 v로 하여 다시 ②과정 반복 수행
③ 스택이 공백이 될 때까지 ②반복 수행
더보기
답 >>>
A - B - D - G - E - C - F
의사 코드(Pseudo code)
DFS(v)
for (i ← 0; i<n; i ← i+1) do {
visited[i] ← false;
}
stack ← createStack();
visited[v] ← true;
while (not isEmpty(stack)) do {
if (visited[v의 인접정점 w] = false) then {
push(stack, v);
visited[w] ← true;
w 방문;
v ← w;
}
else v ← pop(stack);
}
end DFS()
DFS의 특성상 알고리즘은 두 가지 방법으로 구현할 수 있다.
1. 재귀 호출 (Recursion)
2. 스택 (Stack)
Java 코드 구현
1. 재귀 호출
static Stack<Integer> stack = new Stack<>();
static StringBuilder sb = new StringBuilder();
static boolean node[][] = new boolean[n+1][n+1], visited[] = new boolean[n+1];
static void dfs(int v) {
if(visited[v])
return;
sb.append(v+" ");
for(int i=1; i<=n; i++)
if(node[v][i] && !visited[i]) {
visited[i] = true;
dfs(i);
}
}
2. 스택 사용
public static String dfs(int v, boolean node[][]) {
StringBuilder sb = new StringBuilder();
Stack<Integer> stack = new Stack<>();
boolean visited[] = new boolean[n+1];
stack.add(v);
int idx;
while(!stack.isEmpty()) {
idx = stack.pop();
if(visited[idx])
continue;
visited[idx] = true;
sb.append(idx+" ");
for(int i=0; i<n; i++)
if(node[idx][i] && !visited[i])
stack.add(i);
}
return sb.toString();
}
시간 복잡도
- 인접 리스트 = O(N+E)
- 인접 행렬 = O(N^2)
* N = 정점의 수, E = 간선(노드)의 수
대표적인 DFS 사용 예
- 전위 순회(표기법)
- 미로 탐색
- 그래프 사이클 찾기
- 그래프 연결 요소 찾기
- 그 외....
728x90
반응형
'알고리즘 > [JAVA_자바] 알고리즘' 카테고리의 다른 글
[알고리즘] 플로이드-와샬 알고리즘 (Floyd-Warshall Algorithm) - JAVA / 자바 (0) | 2022.02.20 |
---|---|
[알고리즘] 너비 우선 탐색 (Breath First Search, BFS) - JAVA / 자바 (0) | 2022.02.19 |
[알고리즘] 색인 순차 검색 (Index Sequential Search) - JAVA / 자바 (0) | 2022.02.05 |
[알고리즘] 이진 검색 (Binary Search) - JAVA / 자바 (0) | 2022.02.05 |
[알고리즘] 순차 검색 (Sequential Search) - JAVA / 자바 (0) | 2022.02.05 |