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

그래픽 탐색이란?

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

EX) 특정 도시에서 다른 도시로 갈 수 있는지 없는지

 

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

 

정의

루트 노드(혹은 임의의 다른 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

시작 정점부터 가까운 정점을 먼저 방문하고 먼 정점을 나중에 방문하는 방법

즉, 깊게 탐색하기 전에 넓게 탐색하는 것이다.

 

사용하는 곳

두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때.

 

특징

1) 직관적이지 않은 점 - BFS는 시작 노드에서 거리에 따라 단계별로 탐색한다고 본다.

2) 재귀적인 동작을 하지 않는다.

3) 어떤 노드를 방문했는지 여부를 기록하여 무한루프에 빠질 위험을 제거

4) 방문한 노드를 차례적으로 큐에 저장 후 선입선출(FIFO)로 사용한다.

    - 일반적으로 큐를 사용해서 반복적으로 구현하는 것이 잘 작동한다.

 

주의점

그래프 탐색의 경우 어떤 노드를 방문했는지 검사해야 무한루프에 빠질 위험이 없다.

 

동작원리

과정 : 깊이가 1인 모든 노드를 방문 후 싶이가 2인 노드를, 다음엔 3인 노드를 방문하는

           방법으로 더이상 방문할 곳이 없다면 탐색을 마친다.

 

1. a노드(시작노드) 방문 (방문 노드 확인)
   - 큐에 방문 노드를 삽입
   - 초기 큐에는 시작 노드만 자정
     ➡ a 노드 이웃 노드를 모두 방문 후
         이웃의 이웃들을 방문
   
   
2. 큐에서 꺼낸 노두와 인접한 노드들을 모두 차례로 방문
   - 큐에서 꺼낸 노드를 방문
   - 큐에서 꺼낸 노드와 인접한 모드 노드 방문
     (없다면 큐 앞에서 노드를 꺼낸다)
   - 큐에 방문된 노드를 삽입
   
   
3. 큐가 소진될 때 까지 계속 동작

 

 

 

 

 

 

시간 복잡도

• BFS는 그래프 (n개의 정점, e개의 간선)의 모든 간선을 조회한다.
  • 인접 리스트로 표현된 그래프 : O(n + e)
  • 인접 행렬로 표현된 그래프 : O(n ^ 2)
• 즉, 그래프 내에 적은 수의 간선만 갖는 희소 그래프(spare graph)의 경우 인접 행렬보다 인접 그래프가 유리하다