Colin's Blog
[python] 너비 우선 탐색(BFS)

너비 우선 탐색(Breadth-First Search, BFS)은 그래프 탐색 알고리즘 중 하나입니다. BFS는 그래프의 루트 노드에서 시작하여 인접한 모든 노드를 우선적으로 방문한 후, 다음 레벨의 인접한 노드를 방문하는 방식으로 동작합니다.

동작 과정

  1. 시작 노드를 방문 대기열에 추가한다.
  2. 방문 대기열이 비어있을 때까지 다음 과정을 반복한다.
    1. 큐에서 노드 n을 꺼내서 방문한다.
    2. n의 인접한 모든 미방문 노드를 방문 대기열에 추가한다.
    3. 각 인접 노드 v에 대해, v를 n의 부모로 설정한다.

예제 코드

from collections import deque

def bfs(graph, start):
    visited = []
    queue = deque([start])

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.append(node)
            for neighbor in graph[node]:
                queue.append(neighbor)
    
    return visited

예제

다음은 BFS 알고리즘을 사용하여 그래프를 탐색하는 예제입니다.

# 그래프 정의 (인접 리스트로 표현)
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# BFS 탐색 시작
result = bfs(graph, 'A')
print(result)  # ['A', 'B', 'C', 'D', 'E', 'F']

시간 복잡도

BFS의 시간 복잡도는 O(V + E)입니다. 여기서 V는 정점(Vertex)의 수, E는 간선(Edge)의 수를 의미합니다.

참고 문헌

© 2018 Colin. All rights reserved.