CS/알고리즘
알고리즘 - DFS, BFS
빈둥벤둥
2021. 2. 12. 22:23
DFS, BFS
DFS, BFS
-
그래프의 탐색 방법이다.
- 시간복잡도는 노드, 엣지의 개수에 영향을 받으며 DFS, BFS 동일하다.
- 인접 리스트로 구현시 -> O(|v|+|e|)
- 인접 노드로 구현시 -> O(v^2)
DFS - 깊이 우선 탐색
-
재귀적으로 구현한다.
-
모든 노드를 다 탐색해야 최단 거리를 알 수 있으므로 최대 길이, 최대값 등을 찾을때 적합하다.
- 시작 노드로 부터 한 방향으로 계속 탐색을 진행하다가 더 이상 갈 곳이 없을때 되돌아와서 다른 방향으로 다시 탐색한다.
-
트리의 순회에서 중순위 탐색한 결과와 같다.
- 구현 with 자바
1
2
3
4
5
6
7
8
9
|
static void dfs(int[][] node, boolean[] memo, int num) {
memo[num] = true;
for(int i = 1; i < node.length; i++) {
if(node[num][i] == 1 && memo[i] == false) {
dfs(node, memo, i);
}
}
}
|
cs |
BFS - 너비 우선 탐색
- 시작 노드로 부터 도착 노드까지의 최단 거리, 최소값 등을 찾을때 적합하다.
- 시작 노드로 부터 가까운 정점을 먼저 방문하고 멀리있는 정점을 나중에 방문하는 방법이다.
- 레벨 순회 하므로 도착노드를 발견하면 해당 거리가 최단 거리이며 더 이상 탐색하지 않아도 된다.
- 트리의 순회에서 레벨 순회 결과와 같다.
- 구현 with 자바
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
static void bfs(int[][] node, boolean[] memo, int num) {
Queue<Integer> queue = new LinkedList<>();
memo[num] = true;
queue.offer(num);
while(!queue.isEmpty()) {
int temp = queue.poll();
for(int i = 1; i < node.length; i++) {
if(node[temp][i] == 1 && memo[i] == false) {
memo[i] = true;
queue.offer(i);
}
}
}
}
|
cs |
트리 구조 순회 이미지
