반응형
출처: 나무위키
경로 비교
BFS
- Queue 이용
- 최소신장트리(Minimum Spanning Trees), 최단경로(Shortest Paths)
장점: 무한히 깊거나 무한에 가까운 트리인 경우에 효과적
단점: 목표 노드로 가는 경로들 모두가 같은 거리일 때 비효율적
※ BFS (Breadth-First Search, 너비 우선 탐색)
BFS (Breadth-First Search, 너비 우선 탐색)
BFS 그래프 전체를 탐색하되, 인접한 노드들을 차례대로 방문합니다. Queue 이용 * DFS로 풀리는 문제는 일반적으로 BFS로도 풀 수 있습니다. Process ※ 깊이 우선 탐색과는 달리 너비 우선 탐색에서
zoosso.tistory.com
DFS
- Stack 이용
- 백트래킹
- 사이클 탐지(Cycle Detection), 위상 정렬(Topological Sorting)
장점: 공간복잡도가 상대적으로 작음
단점: 목표 노드에 따라 스택오버플로우가 발생할 수 있음
※ DFS (depth-first search, 깊이 우선 탐색)
깊이 우선 탐색(depth-first search, DFS)
DFS 그래프의 모든 정점을 방문할 때 최대한 깊숙히 정점을 방문하는 방식입니다. - Stack 이용 즉, 연결된 정점을 따라 계속 순회하다가 갈 곳이 없어지며 바로 이전단계로 가는 백트래킹 방식.
zoosso.tistory.com
관련 문제
반응형
'알고리즘' 카테고리의 다른 글
| 위상정렬 (Topological sort) (0) | 2021.02.24 |
|---|---|
| 버블 정렬(Bubble Sort) (0) | 2021.02.24 |
| [예제] 합병 정렬 (Merge Sort) (0) | 2021.02.23 |
| 기수 정렬(Radix Sort) (0) | 2021.02.23 |
| 정렬 알고리즘 비교 (0) | 2021.02.23 |
댓글