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

그래프 탐색

• 하나의 정점으로부터 시작해 차례대로 모든 정점들을 한 번씩 방문하는 것

너비 우선 탐색 (BFS)

• 루트 노드 (혹은 다른 임의의 노드)에서 시작해 인접한 노드를 먼저 탐색하는 방법
• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
• 넓게(wide) 탐색
• 두 노드의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용
• BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐색
• 재귀적으로 동작하지 않음
• 어떤 노드를 방문했었는지 여부 반드시 검사해야함 (안하면 무한루프에 빠질 위험 있음)
• 방문한 노드들을 차례로 저장한 후 꺼낼 수 있도록 큐(Queue) 사용

너비 우선 탐색 (BFS) 과정

1. 시작 노드 방문 (방문한 노드 체크)
   • 큐에 방문된 노드 삽입
2. 큐에서 꺼낸 노드와 인접한 모든 노드 차례로 방문
   • 인접한 노드가 없다면 큐의 앞에서 노드 꺼냄
   • 큐에 방문된 노드를 삽입
3. 큐가 비어있을 때까지 계속 반복