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

그래프 탐색이란, 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 단 한번씩 방문하는 것을 의미한다.

그래프 탐색에는 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS) 두 가지의 방법이 있는 데, 그 중에서 너비 우선 탐색에 대해 알아보고자 한다.

 

 

 

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

 

 너비 우선 탐색이란, 인접한 노드들을 차례대로 방문하는 그래프 탐색 방법이다.

 

위 그림은 너비 우선 탐색과 깊이 우선 탐색에 대한 그림이다.

그림과 같이 너비 우선 탐색 트리는 높이가 작은 노드부터 차례대로 탐색하고 더 높은 높이를 탐색한다면, 깊이 우선 탐색은 자신보다 높은 높이의 노드를 탐색한다.

 

너비 우선 탐색은 큐(Queue) 자료구조를 사용한다.

큐를 이용하여 너비 우선 탐색을 구현하는 방식은 아래와 같다.

 

         1. queue의 가장 앞 노드를 enqueue

         2. 현재 노드에 인접한 모든 노드들 중 아직 방문하지 않은 노들을 queue에 dequeue

         3. queue가 비어있지 않으면, 다시 1번 실행

 

큐를 이용한 구현방식에 대한 상세한 예시는 아래와 같다.

 

 

 

큐를 활용한 BFS 예시                                            

 

왼쪽의 그래프를 오른 쪽의 큐를 이용하여 너비 우선 탐색을 실행한다.

각 노드는 오른쪽으로 삽입되어 왼쪽으로 나오게 된다.

시작노드는 A로 가정한다.

 

우선 시작 노드 A를 queue에 삽입한다. 이 후 위에서 설명한 1, 2, 3번의 단계를 따르게 된다.

 

queue의 가장 앞에 위치에 있는 노드, A를 꺼낸다.

이후 A 노드에 인접된 노드들 중 아직 방문하지 않은 B, E, D 노드를 queue에 삽입한다.

편의상 파란색의 노드는 방문 후 탐색이 완료된 노드를, 노란색 노드는 방문 후 아직 큐에 있는 노드로 가정한다.

 

 

이후 queue가 비어있지 않음으로, 이번에는 가장 앞에 있는 B 노드를 꺼내게 된다.

원래라면 B에 인접한 E 노드를 삽입해야겠지만, E 노드는 이미 queue에 존재하는 방문한 노드임으로 삽입하지 않는다.

 

이후 E 노드가 꺼내지고, 방문하지 않은 인접된 노드인 C 노드를 새롭게 queue에 삽입한다.

 

queue의 가장 앞에 존재하는 노드인 D 노드가 꺼내지고, 방문하지 않은 인접 노드가 없으므로 아무 노드도 삽입하지 않는다.

 

이후 C 노드를 꺼내고, queue에 존재하는 노드가 없으므로 탐색을 종료한다.

 

 

 

구현                                

 

아래는 파이썬을 이용하여 너비 우선 탐색을 구현한 코드이다.

def bfs(graph, start):
  visited = [] # 방문한 곳
  queue = [start]
 
  while queue: # queue에 원소가 있을때
    vertex = queue.pop(0) # 큐의 맨 앞의 원소를 방문
 
    if vertex not in visited: # 꼭짓점이 방문된 적이 없다면
      visited.append(vertex)
      for node in graph[vertex]: #  연결된 노드들 중
        if node not in visited: # 방문 안 된 노드를 큐에 추가
          queue.append(node)
 
  return visited

참고로 너비 우선 탐색의 시간 복잡도는  θ( |V| + |E| ) 이다.