그래프 기반 알고리즘
1. 그래프란?
그래프(Graph)는 정점(Vertex)과 간선(Edge)으로 구성된 자료구조로, 여러 개의 노드가 서로 연결된 구조를 표현한다. 그래프는 다음과 같은 방식으로 표현될 수 있다:
- 무방향 그래프: 간선이 방향을 가지지 않는 그래프
- 방향 그래프: 간선이 특정 방향을 가지는 그래프
- 가중 그래프: 간선에 가중치(비용)가 부여된 그래프
2. 그래프 탐색 알고리즘
2.1 깊이 우선 탐색(DFS: Depth-First Search)
DFS는 그래프를 깊게 탐색하는 방식으로, 스택(Stack) 또는 재귀(Recursion)를 활용한다.
수식 표현
DFS 탐색 과정은 다음과 같이 정의할 수 있다:
Python 코드 예제
class Graph:
def __init__(self, vertices):
self.graph = {i: [] for i in range(vertices)}
def add_edge(self, u, v):
self.graph[u].append(v)
def dfs(self, v, visited=None):
if visited is None:
visited = set()
visited.add(v)
print(v, end=' ')
for neighbor in self.graph[v]:
if neighbor not in visited:
self.dfs(neighbor, visited)2.2 너비 우선 탐색(BFS: Breadth-First Search)
BFS는 그래프를 넓게 탐색하는 방식으로, 큐(Queue)를 활용한다.
수식 표현
BFS 탐색 과정은 다음과 같이 정의할 수 있다:
Python 코드 예제
from collections import deque
class Graph:
def __init__(self, vertices):
self.graph = {i: [] for i in range(vertices)}
def add_edge(self, u, v):
self.graph[u].append(v)
def bfs(self, v):
visited = set()
queue = deque([v])
visited.add(v)
while queue:
node = queue.popleft()
print(node, end=' ')
for neighbor in self.graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)3. 최단 경로 알고리즘
3.1 다익스트라 알고리즘 (Dijkstra)
다익스트라 알고리즘은 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다. 가중 그래프에서 동작하며, 음수 가중치는 허용되지 않는다.
수식 표현
Python 코드 예제
import heapq
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
pq = [(0, start)]
while pq:
current_distance, current_node = heapq.heappop(pq)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node]:
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances3.2 플로이드-워셜 알고리즘 (Floyd-Warshall)
모든 정점에서 모든 정점까지의 최단 경로를 찾는 알고리즘이다.
수식 표현
Python 코드 예제
def floyd_warshall(graph):
dist = [[float('inf')] * len(graph) for _ in range(len(graph))]
for i in range(len(graph)):
dist[i][i] = 0
for u in range(len(graph)):
for v, w in graph[u]:
dist[u][v] = w
for k in range(len(graph)):
for i in range(len(graph)):
for j in range(len(graph)):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist4. 최소 신장 트리 (MST)
4.1 크루스칼 알고리즘 (Kruskal)
그래프의 모든 정점을 연결하는 최소 비용의 트리를 구하는 알고리즘으로, 간선을 정렬한 후 유니온-파인드(Union-Find)를 사용한다.
수식 표현
Python 코드 예제
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
def find(self, u):
if self.parent[u] != u:
self.parent[u] = self.find(self.parent[u])
return self.parent[u]
def union(self, u, v):
root_u = self.find(u)
root_v = self.find(v)
if root_u != root_v:
self.parent[root_v] = root_u
def kruskal(edges, n):
mst = []
uf = UnionFind(n)
edges.sort(key=lambda x: x[2])
for u, v, w in edges:
if uf.find(u) != uf.find(v):
uf.union(u, v)
mst.append((u, v, w))
return mst이 문서는 그래프 알고리즘을 설명하고, 각 알고리즘의 개념, 수식, 그리고 Python 구현 예제를 제공하였다. 그래프 이론은 경로 탐색, 네트워크 분석, AI 경로 탐색 등 다양한 분야에서 활용되므로, 주요 알고리즘을 익혀두는 것이 중요하다. 🚀
