그래프(Graph) 알고리즘

9.1 그래프의 표현 방법

1. 인접 행렬 (Adjacency Matrix)

• 정의: 2차원 배열로 노드 간 연결 관계를 표현
• 장점: 연결 확인이 빠름 (O(1))
• 단점: 메모리 소모 큼 (O(n²))

# 무방향 그래프 예시
adj_matrix = [
    [0, 1, 1, 1],  # 0번 노드 → 1,2,3 연결
    [1, 0, 0, 1],  # 1번 노드 → 0,3 연결
    [1, 0, 0, 1],  # 2번 노드 → 0,3 연결
    [1, 1, 1, 0]   # 3번 노드 → 0,1,2 연결
]

2. 인접 리스트 (Adjacency List)

• 정의: 각 노드마다 연결된 노드 리스트를 저장
• 장점: 메모리 효율적 (O(n+e))
• 단점: 연결 확인이 느림 (O(n))

# 무방향 그래프 예시 (0번 노드 → 1,2,3 연결)
graph = {
    0: [1, 2, 3],
    1: [0, 3],
    2: [0, 3],
    3: [0, 1, 2]
}

 

9.2 최단 경로 알고리즘

1. 다익스트라 (Dijkstra)

• 용도: 한 노드 → 다른 모든 노드 (음수 가중치 불가)
• 동작: 우선순위 큐로 최소 거리 노드 선택

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    heap = [(0, start)]
    
    while heap:
        current_dist, node = heapq.heappop(heap)
        if current_dist > distances[node]:
            continue
        for neighbor, weight in graph[node].items():
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(heap, (distance, neighbor))
    return distances

2. 벨만-포드 (Bellman-Ford)

• 용도: 음수 가중치 허용, 한 노드 → 다른 모든 노드
• 동작: 모든 간선을 V-1번 갱신

def bellman_ford(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    
    for _ in range(len(graph)-1):
        for u in graph:
            for v, w in graph[u].items():
                if distances[u] + w < distances[v]:
                    distances[v] = distances[u] + w
    return distances

3. 플로이드-워셜 (Floyd-Warshall)

• 용도: 모든 노드 쌍 간의 최단 경로
• 동작: 3중 반복문으로 모든 경로 고려

def floyd_warshall(graph):
    n = len(graph)
    dist = [[float('inf')] * n for _ in range(n)]
    
    for i in range(n):
        dist[i][i] = 0
        for j, w in graph[i].items():
            dist[i][j] = w
            
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

 

9.3 최소 신장 트리 (MST)

1. 크루스칼 (Kruskal)

• 동작: 간선 정렬 후 사이클 없이 선택 (Union-Find 사용)

def kruskal(edges, n):
    edges.sort()  # (가중치, u, v)
    parent = list(range(n))
    mst = []
    
    def find(u):
        if parent[u] != u:
            parent[u] = find(parent[u])
        return parent[u]
    
    for w, u, v in edges:
        if find(u) != find(v):
            mst.append((u, v, w))
            parent[find(u)] = find(v)
    return mst

2. 프림 (Prim)

• 동작: 시작 노드에서 가장 가까운 노드 확장 (우선순위 큐)

import heapq

def prim(graph, start):
    visited = set([start])
    edges = [(weight, start, neighbor) for neighbor, weight in graph[start].items()]
    heapq.heapify(edges)
    mst = []
    
    while edges:
        weight, u, v = heapq.heappop(edges)
        if v not in visited:
            visited.add(v)
            mst.append((u, v, weight))
            for neighbor, w in graph[v].items():
                if neighbor not in visited:
                    heapq.heappush(edges, (w, v, neighbor))
    return mst

 

9.4 위상 정렬 (Topological Sort)

• 용도: DAG(Directed Acyclic Graph)에서 노드 순서 정렬
• 동작: 진입 차수 0인 노드부터 제거 (BFS 사용)

from collections import deque

def topological_sort(graph):
    in_degree = {u:0 for u in graph}
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1
    
    queue = deque([u for u in in_degree if in_degree[u] == 0])
    result = []
    
    while queue:
        u = queue.popleft()
        result.append(u)
        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    return result if len(result) == len(graph) else "Cycle exists!"

 

9.5 네트워크 플로우 (Network Flow)

에드몬드-카프 (Edmonds-Karp)

• 용도: 소스 → 싱크 최대 유량 계산 (BFS로 증가 경로 탐색)

from collections import deque

def edmonds_karp(graph, source, sink):
    max_flow = 0
    residual = {u: {} for u in graph}
    for u in graph:
        for v, cap in graph[u].items():
            residual[u][v] = cap
            residual[v][u] = 0  # 역방향 간선 초기화

    while True:
        parent = {}
        queue = deque([source])
        while queue:
            u = queue.popleft()
            for v in residual[u]:
                if residual[u][v] > 0 and v not in parent:
                    parent[v] = u
                    queue.append(v)
                    if v == sink:
                        break
        if sink not in parent:
            break
        
        path_flow = float('inf')
        v = sink
        while v != source:
            u = parent[v]
            path_flow = min(path_flow, residual[u][v])
            v = u
        
        v = sink
        while v != source:
            u = parent[v]
            residual[u][v] -= path_flow
            residual[v][u] += path_flow
            v = u
        
        max_flow += path_flow
    return max_flow

 

각 알고리즘 비교 표

알고리즘 용도 시간 복잡도 특징

다익스트라	단일 출발 최단 경로	O((V+E) log V)	음수 가중치 불가
벨만-포드	단일 출발 (음수 허용)	O(VE)	음수 사이클 감지 가능
플로이드-워셜	모든 쌍 최단 경로	O(V³)	모든 노드 쌍 계산
크루스칼	MST	O(E log E)	간선 정렬 + Union-Find
프림	MST	O(E log V)	우선순위 큐 사용
위상 정렬	DAG 순서 정렬	O(V+E)	진입 차수 관리
에드몬드-카프	최대 유량	O(VE²)	BFS로 증가 경로 탐색