[자료구조와 알고리즘] DFS, BFS

그래프의 탐색 : 그래프에서 모든 정점들을 중복 없이 한 번씩 방문하는 방법

일반적인 탐색 방법으로 DFS(깊이우선탐색)과 BFS(너비우선탐색)이 있다.

 

두 탐색 방식의 이해는 유튜브 영상 하나를 보며 하게 되었는데 정리가 잘 되어있어 이해하기 쉬웠다.

https://youtu.be/_hxFgg7TLZQ

---

깊이 우선 탐색 (DFS, Depth-First Search)

한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색 진행된다.

DFS는 Stack을 이용해 구현하게 된다.

노드가 확장되는 순서

 

---

너비우선탐색(BFS, Breadth-First Search)

깊이가 1인 모든 노드를 방문하고 나서 그 다음에는 깊이가 2인 모든 노드를, 그 다음에는 깊이가 3인 모든 노드를 방문하는 식으로 계속 방문하다가 더 이상 방문할 곳이 없으면 탐색을 마친다.

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 

BFS는 Queue를 이용해 구현하게 된다.