Concepts_Lecture.ko.md

11주차 이론 — 그래프 알고리즘 I

레포지토리 안내 | English | 한국어

최종 수정일: 2026-11-04

Introduction to Algorithms, Cormen, Leiserson, Rivest, and Stein, Ch 21, 22, 23

학습 목표:

1. 그래프 $G = (V, E)$를 정의하고 방향과 무방향, 가중치와 무가중치 변형을 구분하며, 인접 행렬(Adjacency Matrix), 인접 리스트(Adjacency List), 인접 배열(Adjacency Array) 표현을 공간과 간선 조회 비용 측면에서 비교할 수 있다
2. DFS와 BFS를 구현하고 추적하며, 두 알고리즘이 모두 $O(V + E)$로 동작함을 설명할 수 있다
3. BFS가 무가중치 그래프에서 최단 홉 수(hop-count) 경로를 찾는다는 것을 설명하고 정당화할 수 있다
4. 방향 비순환 그래프(DAG)를 정의하고, in-degree 0 방법 또는 DFS finish-time 방법으로 위상 정렬(topological order) 을 만들 수 있다
5. 최소 신장 트리(MST) 를 정의하고 모든 MST가 정확히 $|V|-1$개의 간선을 가짐을 증명하며, Prim 알고리즘과 Kruskal 알고리즘을 실행하고 각각의 정당성을 부여하는 그리디 선택을 추론하며 실행 시간을 분석할 수 있다
6. 그래프의 밀도와 간선 중심, 정점 중심의 접근 패턴에 따라 적절한 알고리즘과 표현을 선택할 수 있다

---

목차

• 1. 그래프 기초와 표현
  • 1.1 그래프란?
  • 1.2 그래프의 유형
  • 1.3 인접 행렬
  • 1.4 인접 행렬: 방향 그래프와 가중치 그래프 예시
  • 1.5 인접 행렬: 분석
  • 1.6 인접 리스트
  • 1.7 인접 리스트: 분석
  • 1.8 인접 배열
  • 1.9 표현 방식 비교
• 2. 그래프 순회: BFS와 DFS
  • 2.1 모든 정점 방문
  • 2.2 DFS: 알고리즘
  • 2.3 DFS: 단계별 예시
  • 2.4 DFS: 상세 추적
  • 2.5 BFS: 알고리즘
  • 2.6 BFS: 단계별 예시
  • 2.7 BFS는 최단 홉 수 경로를 준다
  • 2.8 BFS vs DFS: 비교
• 3. 위상 정렬
  • 3.1 위상 정렬: 정의
  • 3.2 알고리즘 1: In-Degree 방법
  • 3.3 알고리즘 2: DFS 기반 방법
  • 3.4 DFS 위상 정렬: 예시
• 4. 최소 신장 트리 (MST)
  • 4.1 MST: 개념과 동기
  • 4.2 Prim 알고리즘: 아이디어
  • 4.3 Prim 알고리즘: 상세 의사코드
  • 4.4 Prim 알고리즘: 풀이 예시
  • 4.5 Kruskal 알고리즘: 아이디어
  • 4.6 Kruskal 알고리즘: 풀이 예시
  • 4.7 Prim vs Kruskal
• 요약
• 점검 문제

---

1. 그래프 기초와 표현

1.1 그래프란?

그래프(graph) 는 객체 사이의 관계를 정점(vertex) 과 간선(edge) 으로 모델링한다.

• 그래프는 $G = (V, E)$로 나타낸다.
  • $V$는 정점(노드) 의 집합이다.
  • $E$는 간선(연결) 의 집합이다.
• 간선으로 연결된 두 정점을 인접(adjacent) 하다고 한다.

graph TD
    n1(("1")) --- n2(("2"))
    n1 --- n3(("3"))
    n2 --- n3
    n2 --- n4(("4"))
    n3 --- n4

Loading

그림 1. 정점 네 개와 간선 다섯 개로 이루어진 무방향 그래프

응용: 소셜 네트워크, 도로 지도, 회로 설계, 웹 하이퍼링크, 빌드 의존성, 작업 스케줄링, 생물학적 경로 등에 쓰인다.

참고: 그래프가 특별한 이유. 배열이나 트리와 달리 그래프에는 다음 원소나 부모 같은 내장된 관계가 없다. 그래프를 알고리즘적으로 다루려면 먼저 표현 방식을 골라야 하며, 이 선택(행렬 vs 리스트)이 이후 모든 것의 복잡도를 결정한다.

1.2 그래프의 유형

유형	설명	예시
무방향(Undirected)	간선에 방향이 없음	친구 관계
방향(Directed, Digraph)	간선에 방향(화살표)이 있음	웹 하이퍼링크, 선수 과목
가중치(Weighted)	간선에 수치 가중치가 있음	도로 거리, 비용
무가중치(Unweighted)	모든 간선이 동등함	단순 연결성

표 1. 그래프의 네 가지 유형과 예시

graph TD
    subgraph u["Undirected"]
        u1(("1")) --- u2(("2"))
        u1 --- u3(("3"))
        u2 --- u4(("4"))
        u3 --- u4
    end
    subgraph d["Directed"]
        d1(("1")) --> d2(("2"))
        d1 --> d3(("3"))
        d3 --> d4(("4"))
        d4 --> d2
    end
    subgraph w["Weighted"]
        w1(("1")) ---|"5"| w2(("2"))
        w1 ---|"3"| w3(("3"))
        w2 ---|"7"| w4(("4"))
        w3 ---|"2"| w4
    end

Loading

그림 2. 무방향 그래프, 방향 그래프, 가중치 그래프의 예

1.3 인접 행렬

$N = |V|$일 때 $N \times N$ 행렬을 사용한다:

• 원소 $(i, j)$는 간선이 있으면 1, 없으면 0이다.
• 방향 그래프에서는 $(i, j)$가 $i$에서 $j$로 가는 간선을 의미하므로 행렬은 일반적으로 비대칭이다.
• 가중치 그래프에서는 1 대신 가중치를 저장한다.

그림 3. 다섯 정점 무방향 그래프의 인접 리스트 표현과 인접 행렬 표현

Graph:             인접 행렬:
   1 --- 2              1  2  3  4
   |   / |          1 [ 0  1  1  0 ]
   |  /  |          2 [ 1  0  1  1 ]
   | /   |          3 [ 1  1  0  1 ]
   3 --- 4          4 [ 0  1  1  0 ]

그림 4. 무방향 그래프와 대칭 인접 행렬

1.4 인접 행렬: 방향 그래프와 가중치 그래프 예시

방향 그래프에서는 행렬이 대칭이 아니다:

방향 그래프:               인접 행렬:
   1 --> 2                    1  2  3  4
   |     ^                1 [ 0  1  1  0 ]
   v     |                2 [ 0  0  0  0 ]
   3 --> 4                3 [ 0  0  0  1 ]
                          4 [ 0  1  0  0 ]

그림 5. 방향 그래프와 비대칭 인접 행렬

가중치 그래프에서는 행렬이 가중치를 담는다. 간선이 없음은 관례에 따라 $0$ 또는 $\infty$로 나타낸다:

가중치 그래프:             인접 행렬:
   1 --5-- 2                  1   2   3   4
   |       |              1 [ 0   5   3   0 ]
   3       7              2 [ 5   0   0   7 ]
   |       |              3 [ 3   0   0   2 ]
   3 --2-- 4              4 [ 0   7   2   0 ]

그림 6. 가중치 그래프와 가중치를 담은 인접 행렬

1.5 인접 행렬: 분석

장점:

• 이해하고 구현하기 쉽다.
• 간선 $(i, j)$ 존재 여부를 $O(1)$ 에 확인할 수 있다.

단점:

• 간선이 매우 적어도 항상 $O(N^2)$ 공간이 필요하다.
• 초기화만 해도 $\Theta(N^2)$ 시간이 걸린다.
• 희소(sparse) 그래프에는 낭비가 심하다.

예시: 정점이 $10^6$개이고 간선이 $2 \cdot 10^6$개인 그래프를 생각한다.

• 행렬은 $10^{12}$개의 원소를 갖지만 그중 단 $2 \cdot 10^6$개만 0이 아니다(방향 그래프 기준이며, 무방향 그래프라면 행렬이 대칭이므로 $4 \cdot 10^6$개이다).

참고: 적합한 경우. 인접 행렬은 대부분의 정점 쌍이 연결된 밀집(dense) 그래프에 적합하다. 어차피 행렬 칸 대부분이 채워지기 때문이다.

1.6 인접 리스트

정점마다 하나씩, $N$개의 연결 리스트를 사용한다. $i$번째 리스트는 정점 $i$에 인접한 모든 정점을 담는다. 가중치 그래프에서는 각 리스트 노드가 간선 가중치도 함께 저장한다.

Graph:                인접 리스트:
   1 --- 2            1: [2] -> [3]
   |   / |            2: [1] -> [3] -> [4]
   |  /  |            3: [1] -> [2] -> [4]
   | /   |            4: [2] -> [3]
   3 --- 4

그림 7. 무방향 그래프와 인접 리스트

가중치 버전은 (이웃, 가중치) 쌍을 저장한다:

가중치 그래프:        인접 리스트 (정점, 가중치):
   1 --5-- 2          1: [(2,5)] -> [(3,3)]
   |       |          2: [(1,5)] -> [(4,7)]
   3       7          3: [(1,3)] -> [(4,2)]
   |       |          4: [(2,7)] -> [(3,2)]
   3 --2-- 4

그림 8. 가중치 그래프의 인접 리스트

1.7 인접 리스트: 분석

장점:

• 필요한 공간이 간선 수에 비례하여 $O(V + E)$ 이다.
• 낭비되는 슬롯이 없어 간선이 적을 때 이상적이다.
• 한 정점의 이웃을 순회할 때 효율적이다.

단점:

• 간선 존재 질의 $(i, j)$의 비용이 $O(1)$이 아니라 $O(\deg(i))$이다.
• 매우 밀집한 그래프에서는 포인터 추적으로 캐시 성능이 떨어질 수 있다.

참고: 적합한 경우. 인접 리스트는 $E \ll V^2$인 희소 그래프에 적합하다. 대부분의 현실 그래프(소셜 네트워크, 도로 지도, 웹 링크)가 여기에 해당한다.

1.8 인접 배열

각 정점의 연결 리스트를 배열로 바꾸거나, 인덱스 테이블과 함께 하나의 연속된 배열에 모두 패킹한다.

정점별 배열:              패킹된 배열 형태:
   Vertex:  1    2    3    4
   Count:  [2]  [3]  [3]  [2]
                                A = [2,3 | 1,3,4 | 1,2,4 | 2,3]
   1: [2, 3]                    Index: [0, 2, 5, 8, 10]
   2: [1, 3, 4]
   3: [1, 2, 4]
   4: [2, 3]

그림 9. 정점별 배열과 패킹된 배열 형태의 인접 배열

패킹된 형태 읽는 법: Index 배열은 오프셋 테이블이다. 정점을 0부터 센 위치 $i$로 가리키면(정점 1이 $i = 0$), 위치 $i$의 이웃 블록은 A[Index[i] .. Index[i+1]-1]를 차지한다. 예를 들어 2번째 정점은 A[Index[1]..Index[2]-1] = A[2..4] = [1, 3, 4]에 놓인다. 블록 길이 Count[i] = Index[i+1] - Index[i]는 정확히 그 정점의 차수이므로, Index와 Count는 같은 경계를 두 가지로 본 것이다. Index에는 마지막에 항목이 하나 더 있어 마지막 정점의 블록 끝을 정의하며, 무방향 간선 하나가 양쪽 끝점의 블록에 한 번씩 저장되므로 그 값은 $2|E| = 10$이다.

연결 리스트 기반 인접에 비한 장점:

• 포인터 오버헤드가 없어 캐시 친화적이다.
• 이웃이 정렬되어 있으면 이진 탐색으로 간선 존재 여부를 $O(\log \deg)$ 에 확인할 수 있다.
• 성능 임계 환경(그래프 데이터베이스, GPU 작업)의 정적 그래프에 표준적으로 사용된다.

1.9 표현 방식 비교

	인접 행렬	인접 리스트	인접 배열
공간	$O(V^2)$	$O(V + E)$	$O(V + E)$
간선 조회	$O(1)$	$O(\deg)$	$O(\log \deg)$
이웃 순회	$O(V)$	$O(\deg)$	$O(\deg)$
간선 추가	$O(1)$	$O(1)$	$O(\deg)$ (재구성)
적합한 경우	밀집 그래프	희소 그래프	희소, 정적 그래프

표 2. 인접 행렬, 인접 리스트, 인접 배열의 연산 비용과 적합한 경우

핵심: 대부분의 현실 그래프가 희소하므로 실제로는 인접 리스트(또는 배열)가 기본 선택이다. 행렬은 $E$가 $V^2$에 근접하거나 상수 시간 간선 질의가 작업의 대부분일 때만 우위를 점한다.

---

2. 그래프 순회: BFS와 DFS

2.1 모든 정점 방문

모든 정점을 체계적으로 방문하는 근본적인 방법은 두 가지이다:

	BFS (너비 우선 탐색)	DFS (깊이 우선 탐색)
전략	레벨 단위 방문	가능한 한 깊이 먼저
자료구조	큐 (FIFO)	스택 / 재귀 (LIFO)
시간 복잡도	$O(V + E)$	$O(V + E)$

표 3. BFS와 DFS의 전략, 자료구조, 시간 복잡도

graph TD
    n1(("1")) --- n2(("2"))
    n1 --- n3(("3"))
    n1 --- n4(("4"))
    n2 --- n5(("5"))
    n2 --- n6(("6"))
    n4 --- n7(("7"))

Loading

그림 10. 트리에서 BFS와 DFS의 방문 순서

1에서 시작하는 BFS는 1 → 2, 3, 4 → 5, 6, 7 순으로, DFS는 1 → 2 → 5 → 6 → 3 → 4 → 7 순으로 방문한다.

핵심: BFS와 DFS는 거의 모든 그래프 알고리즘의 토대이다. 연결 요소, 사이클 탐지, 위상 정렬, 최단 홉 경로, SCC 분해는 모두 이 둘 중 하나에 약간의 부기(bookkeeping)를 더한 것이다.

2.2 DFS: 알고리즘

DFS(G)
    for each v in V
        visited[v] <- NO
    for each v in V
        if visited[v] = NO then aDFS(v)

aDFS(v)
    visited[v] <- YES                    ... (A)
    for each x in L(v)                   ... (B)
        if visited[x] = NO then aDFS(x)  ... (C)

• (A) $v$를 방문 표시한다. 모든 호출에 걸쳐 $|V|$번 일어나므로 $O(V)$ 이다.
• (B) $v$의 인접 리스트를 스캔한다.
• (C) 미방문일 때만 재귀 호출한다. 각 간선은 최대 두 번 확인되므로(무방향 그래프에서는 각 끝점에서 한 번씩, 방향 그래프에서는 한 번), (B), (C) 줄의 총 작업량은 $O(E)$ 이다.

총 시간: $O(V + E)$.

참고: $V+E$에 선형인 것이 옳은 척도인 이유. 모든 정점과 간선을 적어도 한 번씩 보아야 하는 알고리즘은 $\Omega(V + E)$를 지불해야 한다. DFS는 이 하한에 도달하므로 모든 정점을 보는 작업에 점근적으로 최적이다.

2.3 DFS: 단계별 예시

그림 11. 방향 그래프에서 DFS의 진행과 발견 시각, 종료 시각

Graph:                    인접 리스트:
     2                    1: [2, 3, 4, 6]
    / \                   2: [1, 3]
   1---3                  3: [1, 2, 5]
   |\   \                 4: [1, 6]
   | 6---5                5: [3, 6]
   |/                     6: [1, 4, 5]
   4

그림 12. DFS 예제 그래프와 인접 리스트

정점 1에서 시작하는 DFS:
Step 1: 1 방문, 이웃 2로 이동
Step 2: 2 방문, 이웃 3으로 이동
Step 3: 3 방문, 이웃 5로 이동
Step 4: 5 방문, 이웃 6으로 이동
Step 5: 6 방문, 이웃 4로 이동
Step 6: 4 방문, 백트래킹

순회: 1 → 2 → 3 → 5 → 6 → 4

2.4 DFS: 상세 추적

호출 스택 추적:

aDFS(1)                     visited: {1}
  aDFS(2)                   visited: {1,2}
    aDFS(3)                 visited: {1,2,3}
      aDFS(5)               visited: {1,2,3,5}
        aDFS(6)             visited: {1,2,3,5,6}
          aDFS(4)           visited: {1,2,3,5,6,4}
            neighbors: 1(visited), 6(visited)
            -> return
          -> return
        -> return
      -> return
    -> return
  -> return

각 정점은 정확히 한 번 방문되고, 각 간선은 최대 두 번 확인된다.

2.5 BFS: 알고리즘

BFS(G, s)
    for each v in V - {s}
        visited[v] <- NO
    visited[s] <- YES
    enqueue(Q, s)                       ... (A)
    while Q is not empty
        u <- dequeue(Q)                 ... (A)
        for each v in L(u)              ... (B)
            if visited[v] = NO then
                visited[v] <- YES
                enqueue(Q, v)

• (A) 각 정점은 큐에 최대 한 번 들어가고 나가므로 $O(V)$ 이다.
• (B) 각 인접 리스트는 최대 한 번 스캔되므로 $O(E)$ 이다.

총 시간: $O(V + E)$.

2.6 BFS: 단계별 예시

Graph:                    인접 리스트:
     2                    1: [2, 3, 4, 6]
    / \                   2: [1, 3]
   1---3                  3: [1, 2, 5]
   |\   \                 4: [1, 6]
   | 6---5                5: [3, 6]
   |/                     6: [1, 4, 5]
   4

그림 13. BFS 예제 그래프와 인접 리스트

정점 1에서 시작하는 BFS:

Step 1: 1 dequeue.  이웃 방문: 2, 3, 4, 6
        Queue: [2, 3, 4, 6]       Level 0: {1}

Step 2: 2 dequeue.  이웃 1(방문), 3(방문) → skip
        Queue: [3, 4, 6]          Level 1: {2, 3, 4, 6}

Step 3: 3 dequeue.  이웃 5 미방문 → enqueue
        Queue: [4, 6, 5]

Step 4: 4 dequeue.  모든 이웃 방문 → skip
        Queue: [6, 5]

Step 5: 6 dequeue.  모든 이웃 방문 → skip
        Queue: [5]

Step 6: 5 dequeue.  모든 이웃 방문 → skip
        Queue: []                 Level 2: {5}

순회 순서: 1 → 2 → 3 → 4 → 6 → 5

2.7 BFS는 최단 홉 수 경로를 준다

정점 1에서 시작하면 BFS는 자연스럽게 레벨 단위로 정점을 발견한다:

Level 0: {1}           ← 시작점에서 0 홉
Level 1: {2, 3, 4, 6}  ← 시작점에서 1 홉
Level 2: {5}           ← 시작점에서 2 홉

핵심: 무가중치 그래프에서 BFS는 시작 정점에서 도달 가능한 모든 정점까지의 최단 경로(최소 간선 수)를 찾는다.

증명 개요: 레벨 $\ell$에 대한 귀납법을 쓴다. 정점 $v$를 처음 발견할 때 부모는 레벨 $\ell - 1$에 있고, 더 짧은 경로가 있었다면 $v$가 더 일찍 도달되었을 것이므로 모순이다. 큐의 FIFO 규율이 바로 레벨 $\ell - 1$의 정점을 레벨 $\ell$의 정점보다 먼저 처리하도록 강제한다.

이 최단 경로 성질은 가중치 그래프로 일반화되지 않는다. 비음수 가중치 그래프에서는 Dijkstra 알고리즘(5주차, 12주차)이 필요하다.

2.8 BFS vs DFS: 비교

성질	BFS	DFS
자료구조	큐 (FIFO)	스택 / 재귀 (LIFO)
순서	레벨 단위	가능한 한 깊이
최단 경로	예 (무가중치)	아니오
메모리	큐를 위한 $O(V)$ (최악 폭)	재귀 스택을 위한 $O(V)$ (최악 깊이)
시간	$O(V + E)$	$O(V + E)$
흔한 용도	최단 홉 경로, 레벨별 처리, 홉 제한 웹 크롤링	위상 정렬, 사이클 탐지, SCC(Tarjan/Kosaraju), 미로 풀이

표 4. BFS와 DFS의 성질 비교

두 알고리즘 모두 동일한 점근적 시간을 갖지만 그래프를 탐색하는 순서가 근본적으로 다르다.

---

3. 위상 정렬

3.1 위상 정렬: 정의

전제 조건: 그래프가 방향 사이클이 없는 방향 비순환 그래프(DAG)여야 한다.

정의: 모든 방향 간선 $(x, y)$에 대해 $x$가 $y$보다 앞에 오도록 모든 정점을 선형으로 나열한다.

• 같은 DAG에 대해 여러 유효한 순서가 존재할 수 있다.
• 그래프가 위상 정렬을 가질 수 있는 필요충분조건은 그래프가 DAG인 것이다.

graph LR
    A(("A")) --> B(("B"))
    B --> D(("D"))
    A --> C(("C"))
    C --> D

Loading

그림 14. DAG와 두 가지 유효한 위상 순서

이 DAG에서 A, B, C, D와 A, C, B, D는 모두 유효한 위상 순서이다.

참고: 용례. 위상 정렬은 강의 선수 과목, 빌드 시스템(예: make, ninja), 패키지 매니저, 요리 단계, 스프레드시트 재계산 순서에 쓰인다.

3.2 알고리즘 1: In-Degree 방법

topologicalSort1(G)
    for i ← 1 to n
        in-degree가 0인 정점 u 선택
        A[i] ← u
        그래프에서 정점 u와 그것의 모든 나가는 간선 제거
    // A[1..n]이 위상 순서를 담는다

동작 원리: in-degree가 0인 정점은 그 앞에 와야 할 정점이 없으므로 다음에 배치해도 안전하다. 그 정점을 제거하면 다른 정점의 in-degree가 줄어들 뿐이고 남은 그래프도 DAG이므로, 다음 단계에서도 in-degree가 0인 정점이 존재한다.

구현 팁: in_degree[] 배열과 in-degree 0인 정점들의 큐를 유지하면 알고리즘이 BFS와 비슷한 형태가 되어 $O(V + E)$ 로 동작한다. 이 구현을 Kahn 알고리즘이라고도 부른다.

예시 (라면 레시피):

Step (a): "봉지 뜯기"가 in-degree 0 → 선택, 간선 제거
Step (b): "물 끓이기"가 in-degree 0 → 선택, 간선 제거
Step (c): "면 넣기"가 in-degree 0 → 선택, 간선 제거
   …모든 정점이 배치될 때까지 반복

3.3 알고리즘 2: DFS 기반 방법

topologicalSort2(G)
    for each v in V
        visited[v] ← NO
    for each v in V
        if visited[v] = NO then DFS-TS(v)

DFS-TS(v)
    visited[v] ← YES
    for each x in L(v)
        if visited[x] = NO then DFS-TS(x)
    v를 연결 리스트 R의 맨 앞에 삽입    // 모든 자식 방문 후

• DFS가 한 정점을 끝낼 때(모든 후손이 끝났을 때) 결과 리스트 $R$의 앞쪽에 그 정점을 추가한다.
• 알고리즘이 종료되면 $R$이 위상 순서이다.

시간 복잡도: $O(V + E)$ (DFS와 동일).

참고: 끝날 때 앞에 삽입하는 이유. DAG에서 한 정점은 그것에서 도달 가능한 모든 후손이 이미 $R$에 들어가 있을 때에만 끝난다. 방금 끝난 정점을 $R$의 맨 앞에 두면 그 정점이 자신으로부터 도달 가능한 모든 정점보다 앞에 오게 되며, 이것이 정확히 위상 순서가 요구하는 조건이다.

3.4 DFS 위상 정렬: 예시

그림 15. 옷 입기 DAG의 DFS 발견 시각, 종료 시각과 위상 정렬 결과

DAG:
   A --> B --> D
   |          ^
   v         /
   C -------

A에서 DFS-TS (인접 순서 L(A) = [B, C]로 가정, 즉 B를 C보다 먼저 탐색):
   A 방문 → B 방문 → D 방문
     D 끝   → R = [D]
     B 끝   → R = [B, D]
   C 방문
     D 이미 방문, C 끝 → R = [C, B, D]
   A 끝       → R = [A, C, B, D]

결과: A → C → B → D ✓

그림 16. DAG에 대한 DFS 기반 위상 정렬 추적

핵심: 정점은 그것에서 도달 가능한 모든 정점이 이미 기록된 후에야 앞에 추가된다.

---

4. 최소 신장 트리 (MST)

4.1 MST: 개념과 동기

전제 조건:

• 그래프는 연결 그래프여야 한다. 즉 모든 정점 쌍 사이에 경로가 존재한다.
• 간선은 무방향이고 가중치를 가진다.

트리:

• 트리는 사이클이 없는 연결 그래프이다.
• $n$개 정점의 트리는 정확히 $n - 1$개의 간선을 가진다.

[이산수학] 이산수학에서 귀납법으로 증명하는 트리의 기본 성질에 따르면, 정점이 $n$개인 연결 그래프에 사이클이 없을 필요충분조건은 간선이 정확히 $n - 1$개인 것이고, 트리에 간선 하나를 더하면 사이클이 정확히 하나 생긴다. 앞의 성질은 모든 MST가 $|V| - 1$개의 간선을 갖는 이유이고, 뒤의 성질은 점검 문제 7의 컷 성질 증명에서 쓰는 교환 논증의 근거이다.

$G$의 신장 트리:

• 신장 트리는 $G$의 모든 정점을 포함하고 $G$의 간선만 사용하는, 트리인 부분 그래프이다.

최소 신장 트리(MST):

• MST는 $G$의 모든 신장 트리 중 간선 가중치 총합이 최소인 신장 트리이다.

graph TD
    A(("A")) ---|"5"| B(("B"))
    A --- C(("C"))
    A --- D(("D"))
    B --- C
    B --- D
    C ---|"3"| D

Loading

그림 17. 모든 도시를 최소 도로 비용으로 연결하는 MST 문제

목표는 가장 적고 저렴한 도로로 모든 도시를 연결하는 것이다. MST는 그래프를 연결 상태로 유지하면서 가중치 총합이 최소인 n-1개의 간선을 선택한다.

참고: 놀라운 사실. MST는 그리디 알고리즘이 최적임을 증명할 수 있는 몇 안 되는 최적화 문제 중 하나이다. 그리디 선택을 정당화하는 것은 컷 성질(cut property) 이다. $V$를 $(S, V \setminus S)$로 분할한 임의의 컷에서 그 컷을 건너는 최소 가중치 간선은 어떤 MST에 속한다. Prim과 Kruskal은 이 성질을 적용하는 두 가지 다른 방법이다.

4.2 Prim 알고리즘: 아이디어

전략: 하나의 루트에서 시작해 MST를 정점 단위로 키운다.

Prim(G, r)
    S ← empty set
    정점 r 방문 표시; S에 r 추가
    while S ≠ V
        S와 V - S를 잇는 최소 가중치 간선 (x, y) 찾기 (x ∈ S, y ∈ V - S)
        y 방문 표시; S에 y 추가

• 매 단계에서 컷 $(S, V \setminus S)$을 건너는 가장 싼 간선을 고른다. 이것이 전형적인 그리디 선택이다.
• 이진 힙으로 최솟값을 추출하면 $O(E \log V)$ 이다.
• 피보나치 힙을 사용하면 $O(E + V \log V)$이며, 이론적으로 밀집 그래프에 더 좋다.

4.3 Prim 알고리즘: 상세 의사코드

Prim(G, r)                            // G = (V, E), r = 시작 정점
    S ← empty
    for each u in V
        d[u] ← ∞                      // (1) 거리 초기화
    d[r] ← 0                          // (2) 시작 정점 거리 = 0
    while S ≠ V                       // (3) |V|번 반복
        u ← extractMin(V - S, d)      // (4) 가장 가까운 fringe 정점
        S ← S ∪ {u}                   // (5) MST 집합에 추가
        for each v in L(u)            // (6) 이웃 relax
            if v in V - S and w(u, v) < d[v] then
                d[v] ← w(u, v)        // (7) 더 싼 연결로 갱신
                tree[v] ← u           // MST의 부모 기록

• fringe 정점은 아직 트리에 속하지 않지만 ($v \in V - S$) $S$에 이미 들어간 어떤 정점과 인접한 정점이다. 즉 자라나는 MST의 경계에 놓인 후보로, $d[v]$가 유한하다.
• extractMin은 힙을 사용하여 추출당 $O(\log V)$이고, 총 $V$회 추출하므로 $O(V \log V)$이다.
• 의사코드 (7)의 이완(relaxation) 은 $S$에서 $v$로 가는 더 싼 간선이 있으면 $d[v]$를 갱신한다. 각 간선은 최대 한 번의 decrease-key를 유발하므로 모든 반복에 걸친 비용은 $O(E \log V)$이다. decrease-key는 힙에 이미 저장된 키를 낮추는 우선순위 큐 연산으로, 비용은 $O(\log V)$이다.
• 총: $O(E \log V)$.

참고: 배열 변형. extractMin을 힙 없이 미방문 정점들의 $d[]$를 단순 선형 탐색하는 방식으로 구현하면, $V$번의 추출이 각각 $O(V)$ 비용을 가져 전체 $O(V^2)$ 가 된다. 이는 밀집 그래프($E$가 $V^2$에 근접)에서 힙 버전보다 더 빠르다. 그 경우 $V^2 \leq E \log V$이기 때문이며, 점검 문제 10에서 다루는 트레이드오프이다.

4.4 Prim 알고리즘: 풀이 예시

graph TD
    A(("A")) ---|"8"| B(("B"))
    A ---|"3"| C(("C"))
    A ---|"5"| D(("D"))
    B ---|"9"| D
    B ---|"7"| E(("E"))
    C ---|"2"| D
    C ---|"4"| E
    D ---|"6"| E

Loading

그림 18. Prim 알고리즘 예제의 가중치 그래프

실행 추적 (A에서 시작):

Step 0: S={A}     d: A=0, B=∞, C=∞, D=∞, E=∞
        A에서 relax: d[B]=8, d[C]=3, d[D]=5

Step 1: extractMin → C (d=3).  S={A, C}
        C에서 relax: d[D] = min(5,2) = 2,  d[E] = 4
        MST 간선: A-C  (가중치 3)

Step 2: extractMin → D (d=2).  S={A, C, D}
        D에서 relax: d[B] = min(8,9) = 8 (변경 없음),  d[E] = min(4,6) = 4 (변경 없음)
        MST 간선: C-D  (가중치 2)

Step 3: extractMin → E (d=4).  S={A, C, D, E}
        E에서 relax: d[B] = min(8,7) = 7
        MST 간선: C-E  (가중치 4)

Step 4: extractMin → B (d=7).  S={A, C, D, E, B}
        MST 간선: E-B  (가중치 7)

MST 가중치 총합: 3 + 2 + 4 + 7 = 16

결과 MST:

graph TD
    A(("A")) ---|"3"| C(("C"))
    C ---|"2"| D(("D"))
    C ---|"4"| E(("E"))
    E ---|"7"| B(("B"))

Loading

그림 19. Prim 알고리즘으로 얻은 MST

4.5 Kruskal 알고리즘: 아이디어

전략: 모든 간선을 가중치 순으로 정렬한다. 가장 싼 간선을 차례로 추가하되, 사이클을 만드는 간선은 건너뛴다.

Kruskal(G)
    T ← empty set                       // MST 간선
    n개의 singleton 집합 생성 (정점당 하나)
    모든 간선 Q를 가중치 오름차순으로 정렬
    while |T| < n - 1
        Q에서 최소 가중치 간선 (u, v) 추출
        if u와 v가 서로 다른 집합에 있으면
            두 집합 Union
            T ← T ∪ {(u, v)}

• 사이클 탐지에는 Union-Find(Disjoint Set) 자료구조를 사용한다.
  • Find(x)는 $x$가 속한 컴포넌트를 찾는다. 경로 압축과 union-by-rank를 함께 쓰면 분할 상환(amortized) $O(\alpha(V))$ 시간이 걸린다.
  • Union(x, y)는 두 컴포넌트를 병합하며, 같은 조건에서 분할 상환 $O(\alpha(V))$ 시간이 걸린다.
• 간선 정렬은 $O(E \log E) = O(E \log V)$이다($E \leq V^2$이므로).

총 시간: $O(E \log V)$.

참고: Union-Find 입문. 각 컴포넌트를 부모 포인터 트리로 유지한다. Find는 루트까지 따라가고, Union은 한 루트를 다른 루트 아래에 연결한다. 경로 압축은 Find 도중 트리를 평탄화하고, union-by-rank는 더 낮은 트리를 더 높은 트리 아래에 연결한다. 둘을 합치면 연산당 분할 상환 비용이 역 Ackermann 함수 $\alpha(V)$가 되어 전체 시간이 거의 선형이 되며, $\alpha(V)$는 상상할 수 있는 모든 $V$에 대해 $\leq 4$이다.

4.6 Kruskal 알고리즘: 풀이 예시

가중치 순 정렬된 간선:
   (C,D,2), (A,C,3), (C,E,4), (A,D,5), (D,E,6), (B,E,7), (A,B,8), (B,D,9)

초기 집합: {A}, {B}, {C}, {D}, {E}

Step 1: 간선 (C,D,2), C와 D가 다른 집합 → ADD
        집합: {A}, {B}, {C,D}, {E}        T = {(C,D)}

Step 2: 간선 (A,C,3), A와 C가 다른 집합 → ADD
        집합: {A,C,D}, {B}, {E}           T = {(C,D),(A,C)}

Step 3: 간선 (C,E,4), C와 E가 다른 집합 → ADD
        집합: {A,C,D,E}, {B}              T = {(C,D),(A,C),(C,E)}

Step 4: 간선 (A,D,5), A와 D가 같은 집합 → SKIP (사이클 형성)

Step 5: 간선 (D,E,6), D와 E가 같은 집합 → SKIP

Step 6: 간선 (B,E,7), B와 E가 다른 집합 → ADD
        집합: {A,B,C,D,E}                 T = {(C,D),(A,C),(C,E),(B,E)}
        |T| = 4 = n-1 → 종료

MST 가중치 총합: 2 + 3 + 4 + 7 = 16

graph TD
    A(("A")) ---|"3"| C(("C"))
    C ---|"2"| D(("D"))
    C ---|"4"| E(("E"))
    E ---|"7"| B(("B"))

Loading

그림 20. Kruskal 알고리즘으로 얻은 MST

MST는 Prim의 결과와 같다. MST가 유일하면 두 알고리즘의 결과가 간선 단위로 일치하고, 가중치에 동률이 있으면 두 알고리즘이 서로 다르지만 모두 최적인 MST를 만들 수 있다.

4.7 Prim vs Kruskal

	Prim	Kruskal
전략	한 정점에서 MST 키우기	전역적으로 가장 싼 간선 선택
자료구조	우선순위 큐 (힙)	Union-Find + 정렬된 간선
시간	$O(E \log V)$	$O(E \log V)$
유리한 경우	밀집 그래프 ($E$가 $V^2$에 근접)	희소 그래프 ($E$가 $V$에 근접)
접근	정점 중심 (컷 확장)	간선 중심 (전역 간선 리스트 스캔)
병렬화	어려움	정렬 단계는 병렬화하기 쉬움

표 5. Prim 알고리즘과 Kruskal 알고리즘의 비교

둘 다 그리디 알고리즘이며 최적성이 증명된 MST를 만든다.

참고: 5주차와의 연결. 그리디 알고리즘은 그리디 선택 성질이 성립할 때 정확히 옳다. MST의 경우 그 정당화가 바로 컷 성질이며, 그리디 휴리스틱이 우연히 정리(theorem)가 되는 드문 최적화 문제 중 하나이다.

최단 경로 알고리즘(Dijkstra, Bellman-Ford, Floyd-Warshall)은 12주차에서 다룬다.

---

요약

개념	핵심 요약
그래프	그래프 $G = (V, E)$는 관계를 계산 가능하게 만드는 방법으로, 정점과 간선으로 관계를 모델링하며 방향과 무방향, 가중치와 무가중치로 나뉜다.
인접 행렬	$O(V^2)$ 공간을 쓰고 간선 조회가 $O(1)$이며, 밀집 그래프에 적합하다.
인접 리스트	$O(V + E)$ 공간을 쓰고 간선 조회가 $O(\deg)$이며, 희소 그래프에 적합하다.
표현 방식 선택	표현 방식이 비용을 결정하므로 밀집 그래프에는 행렬을, 희소 그래프에는 리스트나 배열을 쓴다.
DFS	재귀나 스택으로 가능한 한 깊이 먼저 탐색하며, $O(V + E)$ 시간이 걸린다.
BFS	큐로 레벨 단위 탐색을 하며, $O(V + E)$ 시간에 무가중치 그래프의 최단 홉 경로를 찾는 가장 저렴한 최단 경로 알고리즘이다.
DFS와 BFS의 선택	둘 다 $O(V + E)$이지만 발견 순서가 다르므로 필요한 것(깊이 또는 레벨)에 따라 고른다.
위상 정렬	그래프가 DAG일 때만 존재하며, in-degree 방법이나 DFS finish 방법으로 $O(V + E)$에 구한다.
Prim MST	한 정점에서 MST를 키우고 힙으로 extractMin을 수행하며, $O(E \log V)$ 시간이 걸린다.
Kruskal MST	간선을 정렬하고 Union-Find로 사이클을 피하며, $O(E \log V)$ 시간이 걸린다.
MST의 그리디 최적성	Prim과 Kruskal은 모두 컷 성질로 최적성이 보장되며, 어떤 컷을 보는지가 다르다.
Prim과 Kruskal의 비교	복잡도는 같지만 Prim은 밀집 그래프를, Kruskal은 희소 그래프를 선호한다.

---

점검 문제

1. 표현 선택: 평균 차수 4인 정점 $10^7$개의 도로 네트워크에 어떤 표현을 사용할 것이며 왜 그런가? 각 표현에 필요한 공간을 추정하라.

   정답

   총 간선 수는 $E \approx V \cdot \bar{d}/2 = 10^7 \cdot 4 / 2 = 2 \cdot 10^7$이므로 매우 희소하다($E \ll V^2$). 인접 행렬은 $V^2 = 10^{14}$개 원소(원소당 1바이트 기준 약 100 TB)가 필요해 사용할 수 없다. 인접 리스트나 인접 배열은 $O(V + E)$개 항목, 즉 무방향 간선을 양쪽 끝점에 한 번씩 저장해도 $V + 2E = 5 \cdot 10^7$개 항목(항목당 8바이트 기준 약 400 MB)이면 충분하므로 메모리에 쉽게 들어간다. 따라서 인접 리스트를 사용하며, 캐시 친화성을 위해 패킹된 인접 배열을 써도 좋다. 도로 네트워크는 전형적인 희소 그래프이다.

2. DFS vs BFS 추적: 2.3절의 그래프에서 정점 6부터 시작하는 BFS와 DFS를 실행하라. 둘의 방문 순서를 보고하라.

   정답

   2.3절의 인접 리스트는 1:[2,3,4,6], 2:[1,3], 3:[1,2,5], 4:[1,6], 5:[3,6], 6:[1,4,5]이다. 6에서 BFS: 큐는 [6]으로 시작한다. 6을 dequeue하여 1, 4, 5를 enqueue하고, 1을 dequeue하여 2, 3을 enqueue한다. 4와 5를 dequeue할 때는 이웃이 모두 방문된 상태이고, 그 후 2, 3을 dequeue한다. 순서는 6 → 1 → 4 → 5 → 2 → 3이다. 6에서 DFS: 6을 방문한 뒤 1, 2, 3, 5 순으로 재귀한다(5의 이웃 3과 6은 이미 방문됨). 1까지 백트래킹한 뒤 4를 방문한다. 순서는 6 → 1 → 2 → 3 → 5 → 4이다.

3. BFS 최단 경로 증명: BFS가 정점 $v$를 처음 dequeue할 때 기록된 거리 $d[v]$가 $s$에서 $v$까지의 최단 홉 거리와 같음을 증명하라. FIFO 규율이 정확히 어디서 논증에 들어가는가?

   정답

   $d[v]$에 대한 귀납법을 쓴다. 기저: $d[s] = 0$은 자명하게 최단이다. 귀납: 실제 거리가 $\ell$ 미만인 모든 정점이 올바른 $d$ 값으로 dequeue되었다고 가정한다. BFS가 거리 $\ell - 1$의 $u$를 dequeue하며 이웃 $v$를 처음 발견해 $d[v] = \ell$로 설정한다고 하자. 모순을 위해 $v$의 실제 최단 거리가 $\ell' < \ell$이라 하면, $v$의 실제 BFS 부모는 거리 $\ell' - 1 < \ell - 1$에 있으므로 $u$보다 먼저 dequeue되었을 것이고, 이는 $v$를 $u$에서 처음 발견했다는 가정에 모순이다. FIFO 규율이 결정적인 곳이 바로 이 지점이다. FIFO가 거리 $\ell - 1$의 모든 정점이 거리 $\ell$의 정점보다 먼저 dequeue됨을 보장하므로, 더 짧은 경로가 뒤늦게 끼어들 수 없다.

4. 방향 그래프에서의 DFS: 간선이 ${(A,B), (B,C), (C,A), (A,D)}$인 방향 그래프에 $A$에서 시작하는 DFS를 적용하라. 후행 간선(back edge)을 찾아라. 그것의 존재는 그래프에 대해 무엇을 의미하는가?

   정답

   A에서 DFS를 하면 A, B, C 순으로 진입하고, C의 이웃 A가 DFS 스택 위에 있는(아직 finish하지 않은) 상태이므로 간선 $(C, A)$는 후행 간선(back edge) 이다. C가 반환되고 B가 반환된 뒤 A는 D를 방문한다. 후행 간선의 존재는 방향 그래프에 사이클 $A \to B \to C \to A$가 있음을 의미한다. 일반적으로 방향 그래프가 사이클을 가질 필요충분조건은 DFS가 후행 간선을 적어도 하나 만나는 것이다. 이것이 DFS 기반 사이클 탐지의 원리이며, 이 그래프는 DAG가 아니므로 위상 순서가 존재하지 않는다.

5. 위상 정렬: 간선이 ${(1,2), (1,3), (3,4), (2,4), (4,5)}$인 DAG에 두 위상 정렬 알고리즘을 모두 적용하라. 모든 유효한 위상 순서가 모든 간선 제약을 만족함을 보여라.

   정답

   In-degree 방법: 초기 in-degree는 1:0, 2:1, 3:1, 4:2, 5:1이다. 1을 선택하면 2:0, 3:0이 된다. 2를 선택하면 4:1, 3을 선택하면 4:0, 4를 선택하면 5:0이 되고, 마지막으로 5를 선택한다. 순서는 1, 2, 3, 4, 5이다. DFS 방법: 1에서 1 → 2 → 4 → 5로 내려간다. 5가 끝나 앞에 삽입하면 R=[5], 4가 끝나면 R=[4,5], 2가 끝나면 R=[2,4,5]이다. 3을 방문하면 4는 이미 처리되었으므로 3이 끝나 R=[3,2,4,5]가 되고, 1이 끝나 R=[1,3,2,4,5]가 된다. 두 순서 모두 유효한 이유는 모든 간선 $(x,y)$에 대해 $x$가 $y$보다 앞에 있기 때문이다. 예를 들어 1이 2, 3보다 앞, 2가 4보다 앞, 3이 4보다 앞, 4가 5보다 앞에 있다.

6. 위상 정렬 vs 사이클: 몰래 사이클을 포함하는 그래프에 in-degree 알고리즘을 실행하라. 무엇이 잘못되는가? 알고리즘의 실패 모드로부터 사이클을 어떻게 탐지할 수 있는가?

   정답

   사이클 위 모든 정점은 사이클의 다른 구성원으로부터 들어오는 간선을 적어도 하나 갖는다. 따라서 사이클 외부 정점을 제거하는 것만으로는 사이클 정점의 in-degree가 0이 되지 못한다. 알고리즘은 in-degree 0인 시작점에서 도달 가능한 정점을 처리한 뒤 사이클 정점들을 배치하지 못한 채 멈춘다. 탐지 규칙: 알고리즘 종료 후 배치된 정점 수 < |V|이면 남은 정점들이 사이클을 이루거나 사이클로 들어간다. 이것이 표준적인 선형 시간 DAG 검사이며, Kahn 알고리즘은 $O(V+E)$에 위상 정렬과 사이클 탐지를 동시에 해낸다.

7. MST 컷 성질: 컷 성질을 진술하고 증명하라. 임의의 컷 $(S, V \setminus S)$에 대해 그 컷을 건너는 최소 가중치 간선은 어떤 MST에 속한다. 가중치에 동률이 있을 때 "어떤"이라는 한정사가 왜 중요한가?

   정답

   컷 성질: $(S, V \setminus S)$를 임의의 비자명한 컷이라 하고 $e = (u, v)$를 $u \in S$, $v \in V \setminus S$인 최소 가중치 컷 간선이라 하자. 증명(교환 논증): 임의의 MST $T$를 잡는다. $e \in T$이면 증명이 끝난다. 아니라면 $T$에 $e$를 추가하면 사이클이 생기는데, 이 사이클은 같은 컷을 건너는 또 다른 간선 $e'$를 반드시 포함한다. $w(e) \leq w(e')$이므로 $e'$를 $e$로 교환해 $T' = T \cup {e} \setminus {e'}$를 만들면 $w(T') \leq w(T)$이다. 따라서 $T'$도 MST이며 $e$를 포함한다. "어떤"이라는 한정사가 중요한 이유는 가중치 동률이 있을 때 컷을 건너는 최소 가중치 간선이 여러 개일 수 있고, 서로 다른 MST가 서로 다른 간선을 포함할 수 있기 때문이다. Prim과 Kruskal이 모두 최적이지만 서로 다른 MST를 만들 수 있다.

8. Prim vs Kruskal: 4.4절의 그래프에서 Kruskal을 처음부터 실행하고, 각 단계에서 선택되는 간선을 Prim의 것과 비교하라. 두 알고리즘이 다른 선택을 하는 지점은 어디이며, 그래도 같은 MST가 나오는가?

   정답

   Kruskal 순서(가중치순)는 (C,D,2), (A,C,3), (C,E,4) 선택, (A,D,5) 건너뜀(사이클), (D,E,6) 건너뜀(사이클), (B,E,7) 선택이다. MST = {(C,D), (A,C), (C,E), (B,E)}이고 총 가중치는 16이다. A에서 시작한 Prim은 (A,C,3), (C,D,2), (C,E,4), (E,B,7)을 고른다. 선택된 간선 집합은 동일하며 선택 순서만 다르다. Prim은 A에서 확장하므로 (A,C)를 먼저 고르고, Kruskal은 전역 최소 가중치인 (C,D)를 먼저 고른다. 가중치 동률이 없어 MST가 유일하므로 두 알고리즘은 같은 트리에 수렴한다.

9. Union-Find: 4.6절 예시의 Kruskal 동안 union-by-rank와 경로 압축을 사용해 Find와 Union 연산을 추적하라. 각 단계 후 부모 포인터 숲을 그려라.

   정답

   초기에는 각 정점이 자신의 루트이고 모든 rank가 0이다. (1) (C,D,2): Find(C)=C, Find(D)=D이고 rank가 같으므로 D의 부모를 C로 하고 rank(C)=1로 올린다. 숲은 {A}, {B}, {C←D}, {E}이다. (2) (A,C,3): Find(A)=A(rank 0), Find(C)=C(rank 1)이므로 A를 C 아래에 붙인다. 숲은 {C←D, A}, {B}, {E}이다. (3) (C,E,4): Find(C)=C, Find(E)=E이므로 E를 C 아래에 붙인다. 숲은 {C←D, A, E}, {B}이다. (4) (A,D,5): Find(A)는 A→C로 루트에 닿는다(A의 부모가 이미 루트 C이므로 경로 압축으로 바뀌는 것은 없다). Find(D)도 D→C이다. 루트가 같으므로 건너뛴다. (5) (D,E,6): 둘 다 C를 가리키므로 건너뛴다. (6) (B,E,7): Find(B)=B(rank 0), Find(E)=C(rank 1)이므로 B를 C 아래에 붙인다. 최종 숲은 루트 C에 A, B, D, E를 자식으로 가진 단일 트리이다.

10. 밀도 기반 선택: $V = 1000, E = 999$인 그래프(거의 트리)와 $V = 1000, E = 400{,}000$인 그래프(밀집)에 대해, 각각 어떤 MST 알고리즘을 선호할 것이며 왜인가?

    정답

    희소 케이스($E = 999$): Kruskal. $E \approx V$이므로 $E$개 간선 정렬은 $O(E \log E) \approx 10^4$번의 비교에 그치고 Union-Find의 상수 인자는 거의 1에 가깝다. 실용적으로 매우 빠르고, 정렬 단계는 병렬화하기도 쉽다. 밀집 케이스($E = 400{,}000$, $E \approx V^2/2.5$): Prim(배열 구현). 배열 기반 Prim의 $O(V^2)$ 구현이 Kruskal의 $O(E \log V) \approx 4 \cdot 10^5 \cdot 10 = 4 \cdot 10^6$을 능가하는 이유는 Prim이 $V = 1000$번의 추출만 수행하기 때문이다. 피보나치 힙을 쓰면 Prim은 $O(E + V \log V)$가 되어 밀집 그래프에서 점근적으로 최적이다.