[Algorithm] 너비 우선 탐색 / BFS(Breadth-First Search) 알고리즘

너비 우선 탐색 / BFS (Breadth-First Search) 알고리즘이란?

그래프에서 모든 노드를 방문하는 알고리즘 중 하나이다.

알고리즘의 기본 아이디어는 가까운 노드부터 먼 노드 순으로 그래프를 탐색하는 것이다. 

 

 

시간복잡도

BFS의 시간 복잡도는 그래프의 표현 방식에 따라 달라진다.

 

1. 인접 리스트 사용 시:

• 각 노드에 대해 모든 인접한 노드를 방문해야 한다.
• 각 노드는 한 번씩 방문하며, 각 노드의 모든 인접한 노드를 확인하는 데 걸리는 시간은 인접한 노드의 개수에 비례한다.
• 따라서 시간 복잡도는 O(V + E) 이다.  (* V = 정점의 수, E = 간선의 수)

{
  'A': ['B', 'C', 'D'],
  'B': ['A'],
  'C': ['A', 'D'],
  'D': ['A', 'C', 'E'],
  'E': ['D']
}

 

 

2. 인접 행렬 사용 시

• 어떤 노드에 인접한 노드를 확인하기 위해서는 해당 노드의 모든 이웃을 대상으로 하여 해당하는 행을 전부 확인해야 한다.
• 각 노드를 방문할 때마다 V번의 검사가 이루어지므로, 총 시간 복잡도는 O(V^2)이다.  (* V = 정점의 수)

[
  [0, 1, 1, 1, 0],  # A
  [1, 0, 0, 0, 0],  # B
  [1, 0, 0, 1, 0],  # C
  [1, 0, 1, 0, 1],  # D
  [0, 0, 0, 1, 0]   # E
]

 

 

BFS의 기본 원리

1. 시작 노드 설정:
   • 탐색을 시작할 노드를 선택한다.
2. 방문 처리:
   • 현재 노드를 방문 리스트에 추가하거나, 방문 여부를 나타내는 배열에 체크하며 방문 처리한다. 
3. 인접 노드 탐색:
   • 현재 노드에 인접한 노드 중에서 아직 방문하지 않은 노드를 모두 찾아 큐에 넣는다.
4. 탐색 반복:
   • 큐에서 노드를 꺼내 위 과정을 반복한다.
5. 탐색 종료:
   • 큐가 비었으면 탐색을 종료한다.

 

 

예시

 

 

구현

def bfs(graph, start):
    visited = set()  # 방문한 노드를 추적하기 위한 집합
    queue = deque([start])  # 큐 초기화 및 시작 노드 추가

    while queue:  # 큐가 빌 때까지 반복
        vertex = queue.popleft()  # 큐에서 하나의 노드를 꺼냄
        if vertex not in visited:  # 현재 노드가 방문되지 않았다면
            visited.add(vertex)  # 방문 처리
            print(vertex, end=' ')  # 노드 방문
            # 현재 노드에 연결된 모든 인접 노드를 큐에 추가
            queue.extend([n for n in graph[vertex] if n not in visited])