[Python] 너비 우선 탐색

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

너비 우선 탐색은 그래프와 트리 구조에서 사용되는 탐색 알고리즘임.

시작 정점으로부터 가까운 정점을 탐색하면서 점차 더 멀리 떨어진 정점으로 나아가는 방식으로 동작함.

BFS는 레벨별로 탐색을 진행하며, 큐 자료구조를 이용하여 구현됨.

이 알고리즘은 경로 탐색, 최단 경로 찾기 등 다양한 분야에서 활용됨.

 

BFS의 기본 원리와 과정

1. 초기화

탐색을 시작할 첫 번째 노드를 큐에 삽입하고 방문했다고 표시함.

 

2. 반복 작업

큐에서 노드를 하나 꺼냄.

해당 노드와 인접한 노드들을 확인함.

방문하지 않은 인접 노드를 모든 큐에 삽입하고 방문했다고 표시함.

 

3. 종료 조건

큐가 빌 때까지 위 과정을 반복함.

 

BFS의 특징

1. 완전성

모든 노드를 방문하므로 완전한 탐색을 보장함.

 

2. 최단 경로

가중치가 없는 그래프에서는 최단 경로를 찾을 수 있음.

각 노드는 최초로 방문될 때가 그 노드로의 최단 경로 상태임.

 

3. 시간 복잡도

O(V + E)로, V는 정점의 수, E는 간선의 수임.

모든 노드와 간선을 적어도 한 번씩은 검사하기 때문임.

 

4. 공간 복잡도

최악의 경우 큐는 그래프의 모든 노드를 저장할 수 있어 O(V)임.

 

BFS의 응용

1. 최단 경로와 최소 비용 문제

동일한 비용의 간선을 가진 그래프에서 최단 경로를 찾는 데 이용될 수 있음.

 

2. 사이클 찾기

그래프에 사이클이 있는지 없는지를 판별할 수 있음.

 

3. 연결 요소 찾기

무방향 그래프에서 각 연결 요소를 찾는 데 사용될 수 있음.

 

4. 네트워크 브로드캐스팅

네트워크에서의 정보 전파에 BFS 방식이 효과적임.

 

BFS 구현 예시 (파이썬)

from collections import deque

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=' ')  # 방문한 정점 출력
            # 모든 인접 정점을 큐에 삽입
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    queue.append(neighbor)

# 그래프 예시
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

bfs(graph, 'A')

파이썬의 딕셔너리와 리스트를 이용하여 그래프를 표현하고 BFS를 구현한 것임.

큐를 이용한 반복적인 과정으로 모든 노드를 방문할 수 있음.