그래프의 탐색
BFS(Breathed-First Search)
- 가장 가까운 정점부터 탐색한다.
- 더 탐색할 정점이 없으면 그 다음 떨어져 있는 정점을 방문한다.
- 너비를 우선적으로 탐색하는 방법이다. (너비 우선 탐색)
- 최단 경로를 찾는데 사용된다.
- 최악의 경우 모든 경로를 탐색해야한다.
- 보통 큐로 구현함
DFS(Depth-First Search)
- 하나의 경로를 끝까지 탐색하고 조건에 맞지 않으면 다음 경로를 탐색한다.
- 깊이 우선 탐색이다.
- BFS보다 수행시간은 오래걸릴 수 있지만 노드를 완전히 방문할 수 있다.
- 보통 스택(재귀)으로 구현함