[python] 너비 우선 탐색(BFS)

그래프의 탐색

그래프 탐색은 가장 기본적인 연산으로서 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것이다.

Ex) 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지 연결되어 있지 않은지

 

너비 우선 탐색(BFS: Breath First Search)

너비 우선 탐색이란?

너비 우선 탐색(BFS)은 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 기법이다.

이러한 그래프가 있을 경우 BFS로 어떤 순서가 나오는지 확인해보자.

그래프의 시작 정점인 1에서 시작하여 v(1)을 방문한 후 v(1)에 인접한 정점 v(2)와 v(3)을 방문한 후 v(1)에 더 이상 인접한 간선이 없으므로 해당 단계는 종료된다. 다음에 정점 v(2)와 v(3)과 인접한 정점을 방문한다. 즉, v(2)에 인접한 v(4)와 v(5) 와 v(3)에 인접한 정점인 v(6), v(7)을 방문한다. 결국 마지막 정점인 v(9)에 도착한 후 v(9)에 인접한 간선이 없으므로 전체 탐색이 종료된다.

결국 이 그래프의 탐색 순서는 1 > [2 > 3] > [4 > 5 > 6 > 7] > 8 > 9 이다.

 

너비 우선 탐색의 구현

너비 우선 탐색을 위해서는 가까운 거리에 있는 정점들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐(Queue)가 필요하다. 무조건 큐에서 정점을 꺼내서 정점을 방문하고 인접 정점들을 큐에 추가한다. 큐가 소진될 때까지 동일한 코드를 반복한다.

위의 그래프로 예시를 들어보자면

1. 시작 정점인 1을 큐에 추가한다.
2. 큐에서 1을 꺼내서 방문하고 정점 1의 인접 정점 2, 3을 큐에 추가한다.
3. 큐에서 2를 꺼내서 방문하고 2의 인접 정점 4, 5를 큐에 추가한다.
4. 이미 큐에 들어가 있는 정점은 추가하지 않으며 큐가 공백 상태가 될 때까지 반복한다.

 

데이터

graph = dict()
 
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

 

 

코드1 - 리스트

def bfs_list(graph, start_node):
  need_visited, visited = [], []
  need_visited.append(start_node)
  
  while need_visited:
    node = need_visited[0]
    del need_visited[0]
    
    if node not in visited:
      visited.append(node)
      need_visited.extend(graph[node])
  return visited

 

코드2 - deque

# deque 사용
def bfs_deque(graph, start):
  from collections import deque
  
  visited = []
  need_visited = deque([start])

  
  # 큐가 빌 때까지 반복
  while need_visited:
    node = need_visited.popleft()

    if node not in visited:
      visited.append(node)
      need_visited.extend(graph[node])
      
  return visited

 

너비 우선 탐색의 시간 복잡도

너비 우선 탐색은 그래프가 인접 리스트로 표현되어 있으면 전체 수행시간이 O(n+e)이며(n이 노드의 수, e는 간선의 수이다.), 인접 행렬로 표현되어 있는 경우는 O(n^2)의 시간이 걸린다.

 

장단점

장점으로 너비 우선 탐색은 깊이 별로 모든 정점을 탐색하기 때문에 목표 노드를 찾기까지의 최단 경로를 구할 수 있다. 따라서 모든 정점을 검사하면서 탐색하는 작업에는 해당 탐색을 잘 사용하지 않고 DFS를 사용한다.

단점으로는 탐색 경로가 매우 길 경우 큐에 많은 정보를 저장해야 한다. 따라서 DFS에서보다 많은 저장 공간을 필요로 하기 때문에 메모리 초과가 발생할 수도 있다.

 

 

참고

BFS

[알고리즘 이론] 4. 깊이 우선 탐색(DFS)

C언어로 쉽게 풀어쓴 자료구조

C언어로 쉽게 풀어쓴 자료구조

https://data-marketing-bk.tistory.com/45?category=901221

BFS 완벽 구현하기 - 파이썬

https://brownbears.tistory.com/556

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