그래프 데이터 구조 (Graph Data Structure)
그래프 데이터 구조 (Graph Data Structure)
그래프(Graph)는 정점(vertex, node)과 간선(edge)으로 구성된 비선형 자료구조다. 간선은 두 정점을 연결하며, 네트워크와 같은 관계 구조를 표현할 수 있다.
그래프는 크게 두 가지로 나뉜다.
- 방향 그래프(Directed Graph): 간선이 단방향 관계를 가짐
- 무방향 그래프(Undirected Graph): 간선이 양방향 관계를 가짐
또한 간선에 가중치가 있을 수도, 없을 수도 있다.
- 가중 그래프(Weighted Graph): 각 간선에 비용이나 거리 등의 값이 있음
- 비가중 그래프(Unweighted Graph): 단순히 연결 여부만 표현
그래프는 네트워크 모델링, 웹 페이지 링크 구조, 최단 경로 탐색 등 다양한 분야에서 활용된다.
방향 그래프 (Directed Graph)
방향 그래프는 간선이 특정 방향을 가진다. 예를 들어 도시를 정점으로 두고, 일방통행 도로를 간선으로 표현하면 방향 그래프가 된다.
# 방향 그래프 구현 예시 (인접 리스트)
graph = {
"A": ["B", "C"],
"B": ["D"],
"C": ["D"],
"D": []
}
print(graph)무방향 그래프 (Undirected Graph)
무방향 그래프는 간선이 특정 방향을 가지지 않는다. 즉, 간선은 단순히 두 정점을 연결하며, 양쪽으로 자유롭게 이동할 수 있다.
# 무방향 그래프 구현 예시
graph = {
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A", "D"],
"D": ["B", "C"]
}
print(graph)검색 알고리즘
너비 우선 탐색 (Breadth-First Search, BFS)
BFS는 가까운 정점부터 차례대로 탐색하는 알고리즘이다. 큐(queue)를 활용한다.
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
node = queue.popleft()
if node not in visited:
print(node, end=" ")
visited.add(node)
queue.extend(graph[node])
graph = {
"A": ["B", "C"],
"B": ["D", "E"],
"C": ["F"],
"D": [],
"E": ["F"],
"F": []
}
bfs(graph, "A") # 출력: A B C D E F깊이 우선 탐색 (Depth-First Search, DFS)
DFS는 한 경로를 끝까지 탐색한 후, 막다른 길에서 되돌아오는 방식으로 진행된다. 스택이나 재귀를 이용한다.
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=" ")
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
dfs(graph, "A") # 출력: A B D E F C최단 경로 알고리즘
다익스트라 알고리즘 (Dijkstra's Algorithm)
다익스트라 알고리즘은 음수 가중치가 없는 그래프에서 최단 경로를 찾는 알고리즘이다.
import heapq
def dijkstra(graph, start):
distances = {node: float("inf") for node in graph}
distances[start] = 0
queue = [(0, start)]
while queue:
current_dist, current_node = heapq.heappop(queue)
if current_dist > distances[current_node]:
continue
for neighbor, weight in graph[current_node]:
distance = current_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(queue, (distance, neighbor))
return distances
graph = {
"A": [("B", 1), ("C", 4)],
"B": [("C", 2), ("D", 5)],
"C": [("D", 1)],
"D": []
}
print(dijkstra(graph, "A")) # {'A': 0, 'B': 1, 'C': 3, 'D': 4}벨만-포드 알고리즘 (Bellman-Ford Algorithm)
벨만-포드는 음수 가중치가 있는 그래프도 처리 가능하다. 단, 음수 사이클이 존재하면 무한 루프에 빠질 수 있다.
def bellman_ford(edges, num_vertices, start):
dist = [float("inf")] * num_vertices
dist[start] = 0
for _ in range(num_vertices - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# 음수 사이클 검출
for u, v, w in edges:
if dist[u] + w < dist[v]:
raise ValueError("Negative cycle detected")
return dist
edges = [(0, 1, 4), (0, 2, 5), (1, 2, -3), (2, 3, 4)]
print(bellman_ford(edges, 4, 0)) # [0, 4, 1, 5]최소 신장 트리
프림 알고리즘 (Prim's Algorithm)
프림 알고리즘은 최소 신장 트리(MST)를 찾는 탐욕적 방법이다.
import heapq
def prim(graph, start):
visited = set()
mst = []
edges = [(0, start, start)]
while edges:
cost, u, v = heapq.heappop(edges)
if v not in visited:
visited.add(v)
mst.append((u, v, cost))
for neighbor, weight in graph[v]:
if neighbor not in visited:
heapq.heappush(edges, (weight, v, neighbor))
return mst
graph = {
"A": [("B", 1), ("C", 3)],
"B": [("A", 1), ("C", 1), ("D", 4)],
"C": [("A", 3), ("B", 1), ("D", 2)],
"D": [("B", 4), ("C", 2)]
}
print(prim(graph, "A"))
# [('A', 'A', 0), ('A', 'B', 1), ('B', 'C', 1), ('C', 'D', 2)]크루스칼 알고리즘 (Kruskal's Algorithm)
크루스칼 알고리즘은 간선을 정렬한 후, 사이클이 생기지 않게 최소 비용 간선을 추가해 MST를 만든다.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx != ry:
self.parent[ry] = rx
def kruskal(num_vertices, edges):
uf = UnionFind(num_vertices)
mst = []
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
edges = [(0, 1, 1), (1, 2, 2), (0, 2, 3)]
print(kruskal(3, edges)) # [(0, 1, 1), (1, 2, 2)]마무리
그래프는 현실 세계의 문제를 모델링할 때 굉장히 많이 활용되므로, 각 알고리즘의 특징과 구현 방식을 익혀두는 것이 중요하다.
Server Dev