Python을 활용한 그래프 탐색 알고리즘: BFS와 DFS의 구현

그래프 탐색 알고리즘은 그래프의 모든 노드를 방문하고 탐색하는 기법으로, 네트워크 라우팅, 소셜 네트워킹 사이트, 데이터베이스 설계 등 다양한 분야에서 사용됩니다. Python에서는 너비 우선 탐색(Breadth-First Search, BFS)과 깊이 우선 탐색(Depth-First Search, DFS)를 쉽게 구현할 수 있습니다. 이 글에서는 Python을 이용하여 BFS와 DFS 알고리즘을 구현하는 방법을 소개하겠습니다.

 

너비 우선 탐색 (BFS)

BFS는 가장 가까운 노드를 우선적으로 탐색하고, 점차 멀어지는 순서대로 탐색을 확장합니다. 이 방법은 큐를 사용하여 구현하며, 모든 노드를 레벨별로 탐색합니다. BFS는 최단 경로 문제나 그래프의 연결성을 확인할 때 유용합니다. BFS의 Python 구현은 다음과 같습니다:

 

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            print(vertex, end=' ')
            visited.add(vertex)
            queue.extend(n for n in graph[vertex] if n not in visited)

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

 

 

깊이 우선 탐색 (DFS)

DFS는 가능한 한 깊게 노드를 탐색하며, 스택을 사용하거나 재귀를 통해 구현합니다. 이 방법은 해를 찾는 데 있어 경로를 추적하거나 퍼즐을 푸는 데 사용될 수 있습니다. 다음은 DFS를 재귀적으로 구현한 예제입니다:

 

def dfs(graph, vertex, visited=None):
    if visited is None:
        visited = set()
    visited.add(vertex)
    print(vertex, end=' ')

    for neighbor in graph[vertex]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

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

 

 

이러한 탐색 알고리즘은 각기 다른 시나리오에 따라 적합한 방식을 선택하여 사용할 수 있습니다. BFS는 최단 경로를 찾거나 레벨별로 정보를 필요로 할 때 유용하며, DFS는 경로나 구성의 가능성을 탐색할 때 효과적입니다. Python의 간결한 문법과 강력한 라이브러리 지원 덕분에 이러한 그래프 알고리즘을 쉽게 구현하고 실험할 수 있습니다.