목차
1. 깊이 우선 탐색(DFS)
2. 너비 우선 탐색(BFS)
1. 깊이 우선 탐색(DFS: Depth First Search)
DFS는 시작 정점에서부터 다음 분기까지 해당 분기를 완벽하게 탐색하는 그래프 탐색 기법입니다.
미로를 탐색할 때 한 방향으로 계속 가다가 막히면, 다시 가까운 갈림길로 돌아와 이어가는 것을 예로 들 수 있습니다.
1) 넓게 탐색하는 것이 아닌, 깊게 탐색한다.
3) BFS에 비해 구현이 간단하다.
3) 최단 경로를 보장하지 못한다.
4) BFS에 비해 속도가 느리다.
https://commons.wikimedia.org/wiki/File:Depth-First-Search.gif
2. 너비 우선 탐색(BFS: Breadth First Search)
BFS는 시작 정점을 방문하고 인접한 모든 정점을 방문하는 그래프 탐색 기법입니다.
1) 깊게 탐색하기보단, 넓게 탐색한다.
2) 시작 정점에서 목표 정점까지 최단 거리를 보장한다.
3) DFS보다 구현이 비교적 어렵다.
https://victorqi.gitbooks.io/swift-algorithm/content/breadth-first_search_bfs.html
