그래프를 탐색하는 방법
- 너비 우선 탐색(BFS)
- 깊이 우선 탐색(DFS)
여기서 탐색이란, 하나의 정점으로부터 시작해, 차례대로 모든 정점들을 한 번씩 방문하는 것을 의미한다.
너비 우선 탐색 (BFS : Breadth First Search)
: 가장 인접한 정점 먼저 탐색. 너비를 우선적으로 탐색하는 방법
특징
- 재귀적으로 작동하지 않음
- 답이 되는 경로가 여러개인 경우에도 최단 경로임을 보장.
- 최악의 경우 모든 노드에 대한 정보를 위한 공간을 요구
깊이 우선 탐색 (DFS : Depth First Search)
: 최대한 깊이 탐색한 뒤, 더이상 깊이 탐색할 곳이 없을 경우에 옆으로 이동하여 탐색. 깊이를 우선적으로 탐색하는 방법
특징
- 자기 자신을 호출하는 순환 알고리즘 형태
- 목표 노드가 깊은 단계에 있을 경우, 해를 빠르게 구할 수 있음. 저장 공간의 수요가 비교적 적다
- 해가 없는 경로에서 낭비할 수 있으며, 얻어진 해가 최단 경로라는 보장이 없다.
Sic Parvis Magna 🧩