[알고리즘/Python] BFS(너비우선탐색)

BFS (너비우선탐색)

Breath-First Search, 그래프에서 가까운 부분을 우선적으로 탐색하는 알고리즘이다.

너비 우선 탐색이라고도 한다.

데이터가 N개 있을때 O(N)시간 복잡도를 가진다. 일반적인 경우 실제 수행시간은 DFS보다 좋은편이다.

 

[DFS vs BFS]

	동작 방식	동작 원리	구현	인접한 노드가 여러개라면?
DFS	멀리 있는(깊게 있는)노드 부터 탐색	스택	재귀 함수 이용	한개씩 넣음
BFS	가까운 노드부터 탐색	큐	큐 자료구조 이용	한번에 다 넣음

 

 BFS 동작과정

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.

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

3. 2번과정을 더이상 수행할 수 없을 때까지 반복한다.

 

결과적으로 노드의 탐색순서(큐에 들어간 순서)는 다음과 같다

1->(2->3->8)->(7->4->5)->6

자세히 보면 (2, 3, 4)는 모두 거리가 1이고, (7, 4, 5) 모두 거리가 2이고, 6는 거리가 3이다. 즉, 거리순으로 정렬된다. 이러한 특성을 이용해서 각 간선 비용이 모두 같다는 가정하에 최단거리 문제에도 사용될 수 있다.

 

BFS시간복잡도

• 인접 행렬의 시간 복잡도는 O(N^2)
• 결과적으로 N번만큼 실행되는 for문을 N번 방문하기 때문에 N x N = N^2이다.
• 인접 리스트의 시간 복잡도는 O(E)
• 결과적으로 정점에 연결된 길(간선)만큼 탐색을 하는 for문을 N번 방문하는 것은 모든 정점의 개수를 의미하기 때문에 O(E)이다.

 

BFS 구현 코드

from collections import deque

# BFS
def bfs(graph, start, visited):
  # 큐 구현을 위해 deque라이브러리 사용
  queue = deque([start])

  # 탐색 시작 노드를 방문 처리
  visited[start] = True

  # 큐가 빌 때까지 반복
  while queue:
    # 큐에서 하나의 원소를 꺼내서 출력
    n = queue.popleft()
    print(n, end='')

    # 꺼낸 원소와 인접노드 확인
    for i in graph[n]:
      # 아직 방문하지 않은 노드라면
      if not visited[i]:
        queue.append(i)
        visited[i]=True

# 2차원 맵정보 입력받기
graph=[
  [], # 0번 노드 비우기
  [2,3,8], #1번 노드와 연결된 2,3,8노드
  [1,7],
  [1,4,5],
  [3,5],
  [3,4],
  [7],
  [2,6,8],
  [1,7]
]

# 방문 정보
visited = [False]*(8+1) #(총 노드의 갯수)+인덱스 0
# bfs호출
bfs(graph, 1, visited)