그래프 표현, DFS/BFS, 위상 정렬, MST, 최단경로 알고리즘

**그래프(Graph)**는 현실 세계의 도로망, 사회관계망(SNS), 인터넷 네트워크 등 객체 간의 유기적 관계를 정점(Vertex)과 간선(Edge)으로 모형화한 자료구조입니다.

1. 그래프 탐색: DFS (깊이 우선) & BFS (너비 우선)

# 인접 리스트 그래프
adj = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0, 5],
    3: [1], 4: [1], 5: [2]
}

# 1. DFS (재귀)
visited = [False] * 6
def dfs(v):
    visited[v] = True
    print(v, end=' ')
    for w in adj[v]:
        if not visited[w]:
            dfs(w)

# 2. BFS (Queue)
from collections import deque
def bfs(start):
    visited_b = [False] * 6
    q = deque([start])
    visited_b[start] = True
    while q:
        v = q.popleft()
        print(v, end=' ')
        for w in adj[v]:
            if not visited_b[w]:
                visited_b[w] = True
                q.append(w)

2. 위상 정렬 (Topological Sort)

방향 그래프(DAG, Directed Acyclic Graph)에서 선후 관계를 위배하지 않도록 정점들을 일렬로 나열하는 알고리즘입니다. (진입 차수 indegree 기반)

def topological_sort(graph, n):
    indegree = [0] * n
    for u in graph:
        for v in graph[u]:
            indegree[v] += 1

    q = deque([i for i in range(n) if indegree[i] == 0])
    result = []
    while q:
        u = q.popleft()
        result.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                q.append(v)
    return result

3. 최단 경로: 다익스트라 vs 플로이드-워셜

4. 자주 묻는 질문 (Q&A)

Q. 크루스칼(Kruskal) 알고리즘에서 사이클 형성 여부를 판별하는 방법은? A. Union-Find (서로소 집합, Disjoint-Set) 자료구조를 활용합니다. 두 정점의 루트 노드가 같으면(find(u) == find(v)) 해당 간선 추가 시 사이클이 발생하므로 채택하지 않고 건너뜁니다.