Graph Theory그래프 이론

그래프 G = (V, E)
  V : 꼭짓점(Vertex / Node) 집합
  E : 간선(Edge) 집합, e = (u, v)

예)
  V = {A, B, C, D}
  E = {(A,B), (B,C), (C,D), (A,D)}

무방향 그래프 (Undirected):   A ── B    간선에 방향 없음
방향 그래프 (Directed/Digraph): A ──→ B  간선에 방향 있음

방향 그래프에서:
  진입 차수 (in-degree):  해당 정점으로 들어오는 간선 수
  진출 차수 (out-degree): 해당 정점에서 나가는 간선 수

비가중치 그래프: 연결 여부만 표현 (간선값 = 1로 가정)
가중치 그래프:   간선마다 비용·거리·용량 값 부여

예) 도시 간 거리 그래프:
  서울 ──50km──→ 수원 ──30km──→ 오산

# 정점 수 n, 간선: (0,1), (0,2), (1,2)
n = 3
matrix = [[0] * n for _ in range(n)]

edges = [(0,1), (0,2), (1,2)]
for u, v in edges:
    matrix[u][v] = 1
    matrix[v][u] = 1  # 무방향 그래프

# matrix:
# [[0, 1, 1],
#  [1, 0, 1],
#  [1, 1, 0]]

from collections import defaultdict

graph = defaultdict(list)

edges = [(0,1), (0,2), (1,2), (2,3)]
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)  # 무방향 그래프

# graph: {0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2]}

# 가중치 그래프 (u, v, weight)
wgraph = defaultdict(list)
for u, v, w in [(0,1,4), (0,2,2), (1,2,1)]:
    wgraph[u].append((v, w))
    wgraph[v].append((u, w))

from collections import deque

def bfs(graph: dict, start: int) -> list:
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

# 시간: O(V+E), 공간: O(V)

def dfs(graph: dict, start: int, visited=None) -> list:
    if visited is None:
        visited = set()
    visited.add(start)
    result = [start]
    for neighbor in graph.get(start, []):
        if neighbor not in visited:
            result.extend(dfs(graph, neighbor, visited))
    return result

# 시간: O(V+E), 공간: O(V) (재귀 스택)

import heapq
from collections import defaultdict

def dijkstra(graph: dict, start) -> dict:
    dist = defaultdict(lambda: float('inf'))
    dist[start] = 0
    heap = [(0, start)]

    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:
            continue
        for neighbor, weight in graph.get(node, []):
            nd = d + weight
            if nd < dist[neighbor]:
                dist[neighbor] = nd
                heapq.heappush(heap, (nd, neighbor))

    return dict(dist)

# 시간: O((V+E) log V), 공간: O(V)

def floyd_warshall(n: int, edges: list) -> list:
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w

    for k in range(n):          # 경유 정점
        for i in range(n):      # 출발
            for j in range(n):  # 도착
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

# 시간: O(V³), 공간: O(V²)

def topological_sort(graph: dict) -> list:
    """Kahn 알고리즘 (진입 차수 기반)"""
    in_degree = defaultdict(int)
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1

    queue = deque([n for n in graph if in_degree[n] == 0])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # 결과 길이 != 정점 수이면 사이클 존재
    return result if len(result) == len(graph) else []

# 크루스칼 알고리즘 (Union-Find)
def kruskal(n: int, edges: list) -> int:
    parent = list(range(n))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(a, b):
        a, b = find(a), find(b)
        if a == b:
            return False
        parent[b] = a
        return True

    edges.sort(key=lambda e: e[2])  # 가중치 오름차순
    total = 0
    for u, v, w in edges:
        if union(u, v):
            total += w
    return total

# 시간: O(E log E)

정점 수 V, 간선 수 E

밀집 그래프 (E ≈ V²):  인접 행렬 권장
희소 그래프 (E << V²): 인접 리스트 권장

실전 코딩 테스트: 대부분 인접 리스트 사용
  → graph = defaultdict(list)