[파이썬] 그래프 알고리즘 (Dijkstra, BFS 등)의 이해
그래프 알고리즘은 데이터 구조인 그래프를 사용하여 문제를 해결하는 데 도움이 되는 알고리즘입니다. 그래프는 노드와 간선으로 이루어진 구조로, 다양한 문제를 모델링하여 해결할 수 있습니다. 이번 포스트에서는 그래프 알고리즘 중에서도 Dijkstra와 BFS (Breadth-First Search)에 대해 알아보겠습니다.
Dijkstra 알고리즘
Dijkstra 알고리즘은 하나의 출발점에서 모든 노드까지의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 가중치가 있는 그래프에서 사용됩니다. 각 노드까지의 거리를 계산하면서 최단 경로를 업데이트해가는 방식으로 동작합니다.
아래는 Dijkstra 알고리즘을 사용하여 최단 경로를 구하는 Python 예제 코드입니다.
import heapq
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
queue = [(0, start)]
while queue:
current_distance, current_node = heapq.heappop(queue)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(queue, (distance, neighbor))
return distances
BFS (Breadth-First Search)
BFS (Breadth-First Search)는 그래프의 탐색을 위한 알고리즘으로, 너비 우선 탐색이라고도 합니다. BFS는 루트 노드에서 시작하여 인접한 노드를 모두 탐색한 후에 다음 단계로 진행합니다. 이 알고리즘은 최단 경로를 찾는 데에도 사용될 수 있습니다.
아래는 BFS 알고리즘을 사용하여 그래프를 탐색하는 Python 예제 코드입니다.
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
current_node = queue.popleft()
print(current_node)
if current_node in visited:
continue
visited.add(current_node)
for neighbor in graph[current_node]:
if neighbor not in visited:
queue.append(neighbor)
결론
그래프 알고리즘은 복잡한 문제를 효율적으로 해결하는 데에 아주 유용한 도구입니다. 이번 포스트에서는 Dijkstra와 BFS 알고리즘에 대해 간단히 설명하고 Python 예제 코드를 제시했습니다. 이러한 알고리즘을 활용하여 다양한 문제를 해결할 수 있으며, 실제로 많은 애플리케이션에서 사용되고 있습니다.