BFS, DFS

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

• 그래프 전체를 탐색하는 방법 중 하나로, 루트 노드(또는 다른 임의의 노드)에서 시작하여 인접한 노드를 먼저 탐색한다.
• 시작 정점으로 부터 가까운 정점을 먼저 방문하고, 멀리 떨어져있는 정점을 나중에 방문 순회하며 노드를 넓게 탐색하여 너비 우선 탐색이라고 불리운다.
• 주로 두 노드 사이에 최단 경로 또는 임의의 경로를 찾고 싶을 때 사용한다.
• 주로 Queue라는 자료에 이웃하는 정점을 다 담아놓고 차례대로 pop하여 구현한다.

1-1. BFS의 장점

1. 노드의 수가 적고 깊이가 얕은 경우 빠르게 동작할 수 있다.
2. 단순 검색 속도가 깊이 우선 탐색(DFS)보다 빠르다.
3. 너비를 우선 탐색하기에 답이 되는 경로가 여러개인 경우에도 최단경로임을 보장한다.
4. 최단경로가 존재한다면 어느 한 경로가 무한히 깊어진다해도 최단경로를 반드시 찾을 수 있다.

1-2. BFS의 단점

1. 재귀호출의 DFS와는 달리 큐에 다음에 탐색할 정점들을 저장해야 하므로 저장공간이 많이 필요하다.
2. 노드의 수가 늘어나면 탐색해야하는 노드 또한 많아지기에 비현실적이다.

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

• BFS 와 마찬가지로 그래프 전체를 탐색하는 방법 줌 하나로, 시작점부터 다음 분기로 넘어가기 전에 해당분기를 완벽하게 탐색하고 넘어가는 방법이다.
• 주로 Stack이나 재귀함수를 통해서 구현한다.
• 주의할 점은 무한루프에 빠지지 않기 위해서, 노드를 방문 시 방문 여부를 반드시 검사해야한다.

2-1. DFS의 장점

1. 현재 경로상의 노드들만 기억하면 되므로, 저장 공간의 수요가 비교적 적다.
2. 목표 노드가 깊은 단계에 있는 경우 해를 빨리 구할 수 있다.
3. 구현이 너비 우선 탐색(BFS) 보다 간단한다.

2-2. DFS의 단점

1. 단순 검색 속도는 너비 우선 탐색(BFS) 보다 느리다.
2. 해가 없는 경우에 빠질 가능성이 있다.
3. 깊이 우선 탐색은 해를 구하면 탐색이 종료되므로, 구한 해가 최단 경로가 된다는 보장이 없다.