[알고리즘] BFS

그래프 탐색

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

BFS

Breadth First Seaarch : 너비 우선 탐색

• 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법
• 시작 정점에서 가장 가까운 정점을 먼저 방문하고, 멀리 떨어져 있는 정점은 나중에 방문하는 순회 방법
• 사용 예시 1 : 두 노드 사이의 최단 경로
• 사용 예시 2 : 임의의 경로를 찾고 싶을 때
  
  

DFS와 BFS의 차이

• DFS : 깊이 우선 탐색
• BFS : 너비 우선 탐색

그림을 보면 한눈에 차이점이 보이지 않는가?
DFS는 깊게를 우선으로 탐색하고, BFS 넓게를 우선으로 탐색한다.

그래서 DFS는 재귀로 작성할 수 있겠고, BFS는 그렇지 않다.

BFS의 특징

• 어떤 노드를 방문했는지 여부를 반드시 검사해야함.
• 그래서 방문한 노드들을 차례대로 저장하여 Queue에 저장한다.
  • 선입선출(FIFO)의 방식으로 탐색한다.
  • 큐를 이용해서 반복적 형태로 구현하는 것이 가장 좋다.
• 최단 경로를 탐색하는 'Prim'이나 'Dijkstra' 알고리즘과 유사하다.
  
  

BFS의 과정

1. 큐에 방문한 노드를 넣는다.
2. 큐에서 방문한 노드를 꺼내서 인접한 노드들을 차례로 방문한다.
3. 만약 인접한 노드를 이미 방문했다면, 방문하지 않아도 된다.
4. 큐가 소진될 때까지 계속한다.

BFS 코드

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True # 첫 노드를 방문함
    
    while queue:
        v = queue.popleft()
        
        for i in graph[v]:   # 인접 리스트 탐색
            if not visited[i]:  # 인접한 노드중에서 방문하지 않으면
                queue.append(i)
                visited[i] = True

코드를 살펴보면, queue에서 뽑아낸 값에서 인접 리스트 방식으로 인접한 리스트를 탐색한다.

인접한 노드들을 아직 방문하지 않았으면, queue에 넣고 visited를 체크하는 모습이다.

BFS의 시간 복잡도

• 인접 리스트로 표현된 그래프: O(N+E)
• 인접 행렬로 표현된 그래프: O(N^2)
• 깊이 우선 탐색(DFS)과 마찬가지로 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph) 의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다.
  
  

Reference.

• 너비 우선 탐색 - 나무위키
• [알고리즘] 너비 우선 탐색(BFS)이란