너비 우선 탐색(BFS)

• 그래프 자료 구조에서 원하는 자료를 찾는 탐색 알고리즘 중 하나

• 가까운 노드부터 탐색하는 알고리즘

• 가장 가까운 노드부터 우선 순위를 가져야 하기에, 큐(Queue)를 이용해 구현

• 일반적으로 DFS 보다 수행 시간이 좋음

---

특징

• 모든 간선의 비용이 동일한 조건에서 최단 거리를 구하는 문제를 효과적으로 해결할 수 있는 알고리즘

• 인접한 노드를 반복적으로 큐에 삽입하고 먼저 삽입된 노드부터 차례로 큐에서 꺼내도록 알고리즘을 작성

• 동작과정

  • 탐색 시작 노드를 큐에 삽입하고 방문 처리

  • 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리

  • 위 과정을 수행할 수 없을 때까지 반복

---

장단점

장점

• 목표 노드가 가까울수록 빠르게 도달 가능

• 목표 노르를 찾는다면 해당 답이 최단 경로

단점

• 저장공간이 DFS에 비해 더 필요함

• 노드의 수 전체가 늘어날 수록 비효율적

---

BFS 과정

1. 0번 정점 방문

2. 0번 정점과 인접한 정점 중 가장 값이 작은 1벙 정점 방문

3. 0번 정점과 인접한 정점 중 방문하지 않고, 가장 값이 작은 2번 정점 방문

4. 0번 정점과 인접한 정점 중 방문하지 않고, 가장 값이 작은 3번 정점 방문

5. 0번 정점과 인접한 정점들을 모두 방문하였으므로, 다음 정점인 1번 정점을 기준으러 설정하고, 1번 정잠과 인접한 정점 중 방문하지 않고 가장 값이 작은 4번 정점 방문

6. 1번 정점과 인접한 정점 중 방문하지 않고, 가장 값이 작은 5번 정점 방문

7. 1번과 2번 정점의 인접한 정점들을 모두 방문하였으므로 3번 정점으로 순번이 넘어가고, 3번 정점과 인접한 정점 중 방문하지 않은 6번 정점을 방문

• 더이상 방문할 수 있는 정점이 존재하지 않으므로 종료

• 최종 순서의 경우 0 → 1 → 2 → 3 → 4 → 5 → 6 순서로 방문

---

Code