반응형
DFS
그래프의 모든 정점을 방문할 때 최대한 깊숙히 정점을 방문하는 방식입니다. - Stack 이용
즉, 연결된 정점을 따라 계속 순회하다가 갈 곳이 없어지며 바로 이전단계로 가는 백트래킹 방식.
(깊이 우선 탐색은 탐색의 각 과정에서 가능한 한 그래프 안으로 '깊이' 들어가려고 시도하며,
막힌 정점에 도달하지 않는 한 뒤로 돌아가지 않습니다. 더 따라갈 간선이 없을 경우 이전으로 돌아갑니다.)
특징
- 찾고자 하는 해가 깊은 곳에 있으면 유용하지만 Stack OverFlow에 유의해야 합니다.
- BFS의 경우에는 탐색과정에서 목표를 찾으면 최단경로에 해당되지만
DFS는 최단경로가 아닐 수 있습니다.
DFS와 BFS 비교
출처: 나무위키 경로 비교 BFS - Queue 이용 - 최소신장트리(Minimum Spanning Trees), 최단경로(Shortest Paths) 장점: 무한히 깊거나 무한에 가까운 트리인 경우에 효과적 단점: 목표 노드로 가는 경로들 모..
zoosso.tistory.com
DFS 활용
- 두 정점이 서로 연결 여부
- 연결된 부분집합의 개수
- 그래프에서 Cycle 여부 확인
→ 그래프의 정점을 순회하며 특정 노드를 재방문 여부로 판단
- 위상정렬 (Topological sort)
※ BFS와 달리 DFS는 그래프의 구조에 관련된 다양한 문제를 푸는 데 사용됨
관련 문제
- [SWEA] 1248 공통조상 (Tree 구조에서 DFS)
반응형
'알고리즘' 카테고리의 다른 글
| PS시 자주 사용하는 함수 모음 (0) | 2021.02.28 |
|---|---|
| BFS (Breadth-First Search, 너비 우선 탐색) (0) | 2021.02.27 |
| 최소신장 트리 - 프림(Prim) / 크루스칼(Kruskal) (0) | 2021.02.27 |
| Disjoint-Set & Union-Find (0) | 2021.02.27 |
| 벨만-포드 (Bellman-Ford) (0) | 2021.02.26 |
댓글