7번 · 최소 신장 트리: 크루스칼(Kruskal)과 프림(Prim)
완전 초보자도 용어부터 표의 모든 행, 두 알고리즘의 판별 논리까지 한 편의 한국어 문서로 이어서 읽을 수 있게 구성했습니다.
독일어 원제 확인
7. Graphenalgorithmen (8 Punkte)
이 시험지는 공식 원본·공식 해설이 아니라 2025년 시험 복기 자료다. 7.1의 그래프는 복기표에 적힌 전체 간선과 가중치로 재구성했다. 7.2의 네 패널은 복기 링크에서 다시 확보한 이미지를 사람이 판독해 공통 그래프와 굵은 간선을 복원했으며, 아래 분류는 강의의 Kruskal·Prim 규칙으로 다시 검산한 비공식 해설이다.
선행지식 0에서 시작
이 페이지를 읽는 순서
그래프, 트리, Kruskal, Prim을 한 번도 배운 적 없는 학습자를 대상으로 한다. 위에서 아래로 읽으면 용어 정의, 작은 예제, 실제 표 풀이, 그림 판별, 검산과 연습이 한 페이지 안에서 이어진다.
- 용어를 먼저 고정한다path·cycle·tree·component·cut의 뜻을 먼저 읽고, 모르는 단어를 남긴 채 알고리즘 표로 내려가지 않는다.
- 작은 그래프에서 규칙을 시험한다세 정점 예제로 같은 component를 다시 이으면 왜 cycle이 되는지, cut을 건너는 가장 가벼운 edge가 무엇인지 확인한다.
- 실제 문제는 상태 변화로 읽는다각 행에서 처리 edge, 두 끝점의 component, 선택 또는 거절 이유, 선택 후 forest와 누적 가중치를 차례로 추적한다.
- 답을 가리고 재현한다완성 표와 네 패널 판정을 본 뒤 자가점검의 힌트만 펼쳐 같은 결론과 이유를 스스로 말해 본다.
기호·용어 미니 사전
기호를 외우기보다는, 뒤의 표와 그림에서 각 기호가 어떤 상태를 나타내는지 확인하면 된다.
| 기호/용어 | 한국어 뜻 | 이 문제의 예 |
|---|---|---|
| \(G=(V,E)\) | V는 vertex(정점) 집합, E는 두 정점을 잇는 edge(간선) 집합이다. | 7.1에서는 \(V=\{a,b,c,d,e,f\}\)V={a,b,c,d,e,f}이고 \(\{a,b\}\in E\){a,b}∈E다. |
| \(w(\{u,v\})\) | 간선 {u,v}를 선택할 때 더해지는 비용 또는 가중치다. | \(w(\{a,b\})=1\)w({a,b})=1이고 선택 간선의 weight를 모두 더해 MST 비용 27을 얻는다. |
| \(A\) | 알고리즘이 지금까지 선택한 간선 집합이며, 실행 중에는 forest이고 끝에는 spanning tree가 된다. | 첫 행 뒤 \(A=\{\{a,b\}\}\)A={{a,b}}이고 일곱 번째 행 뒤 선택 간선이 5개다. |
| \(\operatorname{set}(v)\) | 현재 선택 간선만 따라 v에서 도달할 수 있는 모든 정점, 즉 v의 connected component다. | a-b와 b-c를 골랐다면 \(\text{set}(a)=\text{set}(b)=\text{set}(c)=\{a,b,c\}\)set(a)=set(b)=set(c)={a,b,c}다. |
Dazu? / ja / nein / = | Dazu?는 추가 여부, ja는 선택, nein은 거절, =는 바로 윗행의 셀 값을 그대로 복사한다는 시험 표기다. | {a,c}는 같은 component를 이으므로 nein이고 모든 set 셀은 =다. |
| \((S,V\setminus S)\) | 정점 집합을 두 편으로 나눈 cut이며, 한 끝점이 S에 있고 다른 끝점이 V−S에 있으면 그 edge가 cut을 건넌다. | Prim에서 현재 tree 정점 S와 아직 밖의 정점 V−S 사이 최소 edge를 고른다. |
랭크(rank, Union-Find) | Union-Find 내부 tree의 높이에 대한 상한 표식이다. 두 component를 합칠 때 rank가 작은 root를 큰 root 아래에 붙여 tree가 길게 늘어지는 것을 막는다. | 서로 다른 두 singleton의 rank가 같다면 하나를 다른 하나 밑에 붙이고 새 root의 rank를 1 올린다. |
| \(\alpha(|V|)\text{, 상각 분석(amortized)}\) | α는 inverse Ackermann 함수로 현실적인 입력에서 5보다도 작게 자라는 매우 느린 함수다. amortized는 한 번의 최악이 아니라 긴 연산열 전체 비용을 연산 수로 나눈 보장이라는 뜻이다. | path compression과 union by rank를 함께 쓰면 E번의 Find/Union 총비용이 \(O(|E|α(|V|))\)O(|E|α(|V|))라 거의 선형이다. |
시험 문언과 7.1 표는 `AuD Gedächtnisprotokoll SoSe 2025.md` lines 297-319에서 왔다. 이 파일은 비공식 복기다. MST 정의·cut property·Kruskal·Prim은 `Vorlesung\06GraphAlgorithms.pdf` pp.82-117로 검산했고, 표 작성과 네 유형의 비교는 `Übung\AuD26_Sheet10-Sol.pdf` pp.1-5, 13-14를 보조 근거로 사용했다.
먼저 필요한 개념을 0부터
아래 설명은 개념 카드를 따로 암기하는 방식이 아니라, 그래프에서 연결 상태를 추적하고 그 상태로 Kruskal과 Prim을 비교하는 하나의 흐름으로 읽으면 된다.
0. 그래프에서 꼭 알아야 할 말
그래프 \(G=(V,E)\)G=(V,E)는 점들의 집합 V와 점을 잇는 간선들의 집합 E로 이루어진다. 이 문제의 간선은 방향이 없는 undirected edge이며 {a,b}와 {b,a}는 같은 간선이다.
가중치 w({u,v})는 그 간선을 선택할 때 드는 비용이다. 최소 신장 트리는 모든 정점을 연결하면서 총비용이 가장 작은 간선 집합이다.
정점이 |V|개인 트리는 정확히 |V|-1개의 간선을 가진다. 이 문제는 정점이 6개이므로 완성된 spanning tree에는 간선이 5개 있어야 한다.
생활 비유: 여섯 마을에 전선을 놓되 모든 마을이 이어지고 공사비가 최소가 되게 하는 문제다.
1. 연결, 순환(cycle), 연결 성분(component)
두 정점 사이를 선택된 간선들만 따라 이동할 수 있으면 두 정점은 같은 connected component에 있다. 처음에는 간선을 하나도 고르지 않았으므로 각 정점이 혼자 하나의 component다.
이미 같은 component에 있는 두 정점을 다시 잇는 간선을 추가하면 반드시 cycle이 생긴다. Kruskal이 간선을 거절하는 이유는 '가중치가 커서'가 아니라 바로 이 cycle 때문이다.
set(a)는 현재 a와 같은 component에 들어 있는 모든 정점을 뜻한다. a,b,c가 연결되어 있다면 \(\text{set}(a)=\text{set}(b)=\text{set}(c)=\{a,b,c\}\)set(a)=set(b)=set(c)={a,b,c}다.
생활 비유: 서로 전화가 전달되는 사람들은 같은 단체 채팅방에 있다. 같은 방 사람 둘을 또 연결해도 새 사람은 들어오지 않는다.
2. 탐욕적 선택(Greedy)이 뜻하는 것
Greedy algorithm은 매 순간 허용되는 선택 중 지금 가장 좋아 보이는 선택을 한다. Kruskal과 Prim은 모두 greedy이지만 '지금 허용되는 후보'의 범위가 다르다.
Kruskal은 그래프 전체에서 아직 처리하지 않은 가장 가벼운 간선을 보고, cycle만 생기지 않으면 선택한다. 그래서 중간 결과가 여러 조각의 숲(forest)이어도 된다.
Prim은 시작 정점 하나에서 출발해 지금까지 만든 하나의 연결된 tree 바깥으로 나가는 가장 가벼운 간선을 선택한다. 따라서 매 순간 선택된 간선들은 하나의 연결된 덩어리다.
생활 비유: Kruskal은 도시 전체의 최저가 공사부터 계약하고, Prim은 현재 전기가 들어온 지역의 경계에서 가장 싼 확장 공사를 고른다.
7.1 · 크루스칼(Kruskal) 표를 한 줄도 빠짐없이 완성하기
문제를 한국어로 다시 읽기
간선을 가중치 오름차순으로 처리하며, 선택 여부와 각 정점의 component set을 모든 행에 기록한다.
소문제별 독립 개념 강의
왜 이것을 배우는가
Kruskal 표는 단순 암기 문제가 아니라 ‘현재 연결 상태’를 한 행씩 갱신하는 훈련이다. 이 원리를 이해하면 어떤 가중 그래프에서도 cycle을 만들지 않으면서 최소 비용 연결망을 구성하고, 시험 표의 ja·nein·=를 근거와 함께 채울 수 있다.
이 소문제를 마치면: ① path, cycle, tree, forest, spanning tree와 connected component를 서로 구분해 말할 수 있다. ② 각 edge의 두 끝점이 다른 component이면 선택하고 같으면 cycle 때문에 거절하는 이유를 설명할 수 있다. ③ 초기 singleton 상태부터 모든 행의 expanded set, 선택 edge 집합 A, 누적 weight를 재현할 수 있다. ④ Kruskal의 선택이 cut의 light edge이므로 safe하다는 직관으로 결과가 최소임을 설명할 수 있다.
풀이 전에 꼭 알아야 할 말
path(경로)와 cycle(순환)
path는 이웃한 edge를 차례로 따라가는 정점 열이다. cycle은 시작 정점으로 다시 돌아오되 중간 정점을 반복하지 않는 닫힌 path다. 선택 edge에 cycle이 생기면 그중 하나를 빼도 연결이 유지되므로 spanning tree가 될 수 없다.
아주 작은 예: a-b와 b-c가 있으면 a-b-c는 path다. 여기에 c-a를 더하면 a-b-c-a cycle이 된다.
트리·숲·신장 트리(tree, forest, spanning tree)
tree는 connected이면서 cycle이 없는 graph다. forest는 서로 떨어진 tree가 여러 개일 수 있는 acyclic graph다. spanning tree는 원래 graph의 모든 vertex를 포함하는 tree이며 |V|개 정점에 정확히 |V|-1개 edge가 있다.
아주 작은 예: {a,b}와 {c,d} 두 edge는 forest다. 여기에 {b,c}를 더하면 네 정점을 잇는 spanning tree가 된다.
component와 DSU(Union-Find)
component는 현재 선택 edge로 서로 오갈 수 있는 정점 묶음이다. DSU는 MakeSet으로 singleton을 만들고, Find로 두 정점의 대표가 같은지 검사하며, Union으로 서로 다른 두 component를 합치는 자료구조다.
아주 작은 예: Find(a)≠Find(b)이면 {a,b}를 고른 뒤 Union(a,b)를 수행해 \(\text{set}(a)=\text{set}(b)=\{a,b\}\)set(a)=set(b)={a,b}로 만든다.
최소 신장 트리(MST, minimaler Spannbaum)
connected undirected weighted graph의 모든 정점을 잇는 spanning tree 중 선택 edge의 총 weight가 최소인 것이다. edge 수가 |V|-1이라는 사실만으로는 최소성을 보장하지 않으며 Kruskal의 safe-edge 규칙이 필요하다.
아주 작은 예: 정점 6개인 7.1의 MST는 edge 5개이고, 선택 \(\text{weight} 1+2+4+9+11=27\)weight 1+2+4+9+11=27이다.
단체 채팅방을 합치는 가장 싼 케이블 공사
처음에는 여섯 마을이 각각 혼자 있는 채팅방이다. 공사 후보를 가격이 싼 순서로 보고, 서로 다른 채팅방을 잇는 케이블이면 계약해 두 방을 합친다. 이미 같은 방 사람 둘을 또 잇는 케이블은 새 마을을 연결하지 않고 고리만 만들므로 거절한다.
- 마을 한 곳
- 정점(vertex) 한 개
- 같은 채팅방의 마을들
- 현재 연결 성분(connected component), 즉 set(v)
- 두 채팅방을 합치는 케이블
- 다른 연결 성분을 잇는 선택 간선(accepted edge)과 합치기(Union)
- 이미 같은 방을 다시 잇는 불필요한 고리
- 같은 연결 성분의 간선이 만드는 순환(cycle)
비유의 한계: 실제 통신망에는 용량·고장 대비·방향 같은 조건이 있을 수 있지만 이 문제는 오직 undirected edge의 weight 합과 연결 여부만 비교한다.
한 행에서 머릿속으로 보는 네 칸
작은 예제로 먼저 연습 · 세 정점 a,b,c와 edge 1,2,3
vertices={a,b,c}, edges={a,b}:1, {b,c}:2, {a,c}:3이라고 하자. 처음에는 A=∅이고 세 정점이 각각 singleton component다.
- {a,b}:1을 선택
\(\text{set}(a)=\{a\}, \text{set}(b)=\{b\}\)
set(a)={a}, set(b)={b}로 서로 다르므로 cycle 없이 두 component를 합칠 수 있다.이 단계 후 상태: \(A=\{\{a,b\}\}, \text{components}=\{a,b\}|\{c\}, \text{running} \text{weight}=1\)
A={{a,b}}, components={a,b}|{c}, running weight=1 - {b,c}:2를 선택
b는 {a,b}, c는 {c}에 있어 서로 다른 component다. Union 후 모든 정점이 연결된다.
이 단계 후 상태: \(A=\{\{a,b\},\{b,c\}\}, \text{components}=\{a,b,c\}, \text{running} \text{weight}=3\)
A={{a,b},{b,c}}, components={a,b,c}, running weight=3 - {a,c}:3을 거절
a와 c는 이미 a-b-c path로 연결되어 있다. 추가하면 a-b-c-a cycle이 생긴다.
이 단계 후 상태: A 변화 없음, \(\text{components}=\{a,b,c\}, \text{running} \text{weight}=3\)
components={a,b,c}, running weight=3
작은 예제의 결론: 정점 3개에 선택 edge 2개가 있고 connected·acyclic이므로 spanning tree다. 정렬 순서에서 safe edge만 골랐으므로 Kruskal이 만든 MST이며 비용은 3이다.
실제 시험 문제로 연결하기
1. 실제 표를 시작하기 전에 무엇을 적어야 하나?
행 0에 A=∅, running weight=0, set(a)={a}, set(b)={b}, …, \(\text{set}(f)=\{f\}\)set(f)={f}를 적는다. 이 초기 상태가 없으면 첫 Union과 이후 = 표기의 기준을 잃는다.
2. {a,c}:5가 작아 보이는데 왜 nein인가?
그 행이 오기 전에 {a,b}와 {b,c}가 선택되어 a-b-c path가 이미 있다. 따라서 \(\text{set}(a)=\text{set}(c)=\{a,b,c,d\}\)set(a)=set(c)={a,b,c,d}이고 {a,c}를 더하면 a-b-c-a cycle이 생긴다. 절대 weight가 아니라 현재 component가 결정한다.
3. {d,e}:11은 더 비싼데 왜 ja인가?
d는 {a,b,c,d}, e는 {e,f}에 있어 서로 다른 두 component를 잇는다. 지금까지 처리한 더 가벼운 edge로는 이 두 묶음을 연결할 수 없었으므로 이 edge가 필요한 safe edge다.
4. edge 5개를 고른 뒤에도 왜 두 행을 더 쓰나?
알고리즘의 MST는 완성됐지만 원문이 표의 모든 행을 채우라고 요구한다. {d,f}:12와 {c,e}:16은 같은 component를 이으므로 nein이고, 변하지 않는 set 칸에는 =를 쓴다.
5. 이 spanning tree가 왜 minimum인가?
Kruskal은 각 component를 나누는 cut에서 아직 가능한 가장 가벼운 crossing edge를 선택한다. cut property에 따라 그런 light edge는 어떤 MST로 확장 가능한 safe edge이므로, 모든 선택을 반복한 최종 tree는 MST다.
핵심 규칙을 수식으로 읽기
그래프 복원과 최종 최소 신장 트리(MST)
주황색 5개가 선택된 MST 간선이다.
시험지 형식의 완성 답안표
Dazu?는 추가 여부다. \(\text{ja}=\)ja=선택, \(\text{nein}=\)nein=거절, ==윗행과 동일이며 expanded 표에서는 실제 component를 모두 펼쳐 쓴다.
| 간선(edge) | 가중치 w | 선택 여부(Dazu?) | 항목 (set(a)) | 항목 (set(b)) | 항목 (set(c)) | 항목 (set(d)) | 항목 (set(e)) | 항목 (set(f)) |
|---|---|---|---|---|---|---|---|---|
{a,b} | 1 | ja | {a,b} | {a,b} | {c} | {d} | {e} | {f} |
{b,c} | 2 | ja | {a,b,c} | {a,b,c} | {a,b,c} | {d} | {e} | {f} |
{b,d} | 4 | ja | {a,b,c,d} | {a,b,c,d} | {a,b,c,d} | {a,b,c,d} | {e} | {f} |
{a,c} | 5 | nein | = | = | = | = | = | = |
{c,d} | 6 | nein | = | = | = | = | = | = |
{e,f} | 9 | ja | = | = | = | = | {e,f} | {e,f} |
{d,e} | 11 | ja | {a,b,c,d,e,f} | {a,b,c,d,e,f} | {a,b,c,d,e,f} | {a,b,c,d,e,f} | {a,b,c,d,e,f} | {a,b,c,d,e,f} |
{d,f} | 12 | nein | = | = | = | = | = | = |
{c,e} | 16 | nein | = | = | = | = | = | = |
생략 기호 없이 펼친 전체 추적표
0번 초기화부터 시작한다. 누적 가중치 w는 지금까지 선택한 간선(edge)의 가중치(weight) 합이고, 거절 행에서는 변하지 않는다.
한 행씩, 왜 그렇게 되는가
1. {a,b} · 가중치 \(w=1 \to \)w=1 → ja
a와 b는 서로 다른 singleton component다. 선택해도 cycle이 없으므로 합친다.
현재 숲(forest): \(A=\{\{a,b\}\}\)A={{a,b}}
2. {b,c} · 가중치 \(w=2 \to \)w=2 → ja
b는 {a,b}, c는 {c}에 있다. 다른 component를 연결하므로 선택한다.
현재 숲(forest): \(A=\{\{a,b\},\{b,c\}\}\)A={{a,b},{b,c}}
3. {b,d} · 가중치 \(w=4 \to \)w=4 → ja
b는 {a,b,c}, d는 {d}에 있다. 서로 다른 component이므로 선택한다.
현재 숲(forest): \(A=\{\{a,b\},\{b,c\},\{b,d\}\}\)A={{a,b},{b,c},{b,d}}
4. {a,c} · 가중치 \(w=5 \to \)w=5 → nein
a와 c는 이미 {a,b,c,d} 안에서 a-b-c 경로로 연결되어 있다. 추가하면 a-b-c-a cycle이 생긴다.
현재 숲(forest): A는 변하지 않는다.
5. {c,d} · 가중치 \(w=6 \to \)w=6 → nein
c와 d도 이미 같은 component다. 추가하면 c-b-d-c cycle이 생긴다.
현재 숲(forest): A는 변하지 않는다.
6. {e,f} · 가중치 \(w=9 \to \)w=9 → ja
e와 f는 각각 singleton이다. 다른 component를 잇기 때문에 선택한다.
현재 숲(forest): \(A=\{\{a,b\},\{b,c\},\{b,d\},\{e,f\}\}\)A={{a,b},{b,c},{b,d},{e,f}}
7. {d,e} · 가중치 \(w=11 \to \)w=11 → ja
d는 {a,b,c,d}, e는 {e,f}에 있다. 두 큰 component를 잇는 첫 간선이므로 선택한다. 이제 모든 정점이 하나로 합쳐진다.
현재 숲(forest): \(A=\{\{a,b\},\{b,c\},\{b,d\},\{e,f\},\{d,e\}\}\)A={{a,b},{b,c},{b,d},{e,f},{d,e}}
8. {d,f} · 가중치 \(w=12 \to \)w=12 → nein
이미 모든 정점이 같은 component다. d와 f를 더 이으면 cycle이 생긴다. 시험 표가 계속되므로 행은 끝까지 채운다.
현재 숲(forest): A는 변하지 않는다.
9. {c,e} · 가중치 \(w=16 \to \)w=16 → nein
c와 e도 같은 component다. 역시 cycle이므로 거절한다.
현재 숲(forest): A는 변하지 않는다.
풀이의 핵심을 다시 연결하기
- 첫 번째 할 일은 알고리즘을 실행하는 것이 아니라 모든 간선을 가중치 오름차순으로 정렬하는 것이다. 이 표는 이미 1,2,4,5,6,9,11,12,16 순으로 정렬되어 있다.
- 각 행에서 오직 한 질문만 한다. '두 끝점의 현재 set이 같은가?' 다르면 ja와 union, 같으면 nein과 set 유지다. 간선의 절대적인 무게가 크고 작은지는 정렬 순서를 정할 뿐, 같은 행의 ja/nein을 직접 정하지 않는다.
- {a,c}의 무게 5가 비교적 작아도 거절된다. a와 c가 이미 a-b-c로 연결되었기 때문이다. 반대로 {d,e}의 무게 11은 더 크지만 서로 떨어진 두 component를 연결하는 데 필요하므로 선택된다.
- 정점 여섯 개에 선택 간선이 다섯 개가 되었고 모든 정점이 연결되었으므로 MST는 완성되었다. 그러나 문제는 표를 완전히 채우라고 했으므로 남은 무게 12와 16의 행도 nein과 =로 기록해야 한다.
의사코드(pseudocode)
A ← ∅
for each vertex v: MakeSet(v)
sort E by nondecreasing weight
for each edge {u,v} in sorted E:
if Find(u) ≠ Find(v):
A ← A ∪ {{u,v}}
Union(u,v)
return A시간복잡도
- 간선 정렬이 \(O(|E| \log |E|)\)
O(|E| log |E|)이다. - Union-Find를 path compression과 union by rank로 구현하면 모든 Find/Union의 총비용은 \(O(|E| α(|V|))\)
O(|E| α(|V|))에 가깝다. - 전체는 정렬이 지배하여 \(O(|E| \log |E|)\)
O(|E| log |E|)로 쓴다.
의사코드를 한 줄씩 한국어로 풀이
| 코드 | 초보자용 뜻 |
|---|---|
A ← ∅ | 선택 edge 집합을 비운 채 시작한다. |
for each vertex v: MakeSet(v) | 모든 정점을 자기 혼자만 든 singleton component로 만든다. |
간선을 가중치 오름차순으로 정렬: sort E by nondecreasing weight | weight가 작은 edge부터 보도록 정렬한다. 같은 weight는 허용된 tie order를 따른다. |
서로 다른 집합인지 검사: if Find(u) ≠ Find(v) | 두 끝점이 아직 서로 다른 component인지 검사한다. 다를 때만 선택해도 cycle이 없다. |
A ← A ∪ {{u,v}}; Union(u,v) | edge를 A에 넣고 두 component의 모든 정점을 하나의 component로 합친다. |
return A | connected graph에서 선택 edge가 |V|-1개가 되면 A가 MST이며, 시험 표는 요구에 따라 남은 행도 기록한다. |
최종 답과 검산
최소 신장 트리(MST): {a,b}, {b,c}, {b,d}, {e,f}, {d,e}
- 간선 수:\(5=|V|-1\)
5=|V|-1 - 모든 a,b,c,d,e,f가 하나의 component
- 선택 과정에서 cycle 없음
- 총가중치:\(1+2+4+9+11=27\)
1+2+4+9+11=27
시험 답안 템플릿
간선을 가중치 오름차순으로 처리한다. Find(u)≠Find(v)이면 ja 후 Union, 같으면 cycle이므로 nein이다. 선택 간선은 {a,b},{b,c},{b,d},{e,f},{d,e}, 총가중치는 27이다. 이후 {d,f},{c,e}도 같은 component이므로 nein과 =로 끝까지 기록한다.
풀이 후 검산
- 구조 검산: a,b,c,d,e,f가 하나의 component이고 선택 edge 수가 \(5=|V|-1\)
5=|V|-1이며 선택 과정에 cycle이 없다. - 비용 검산: accepted weight만 더해 \(1+2+4+9+11=27\)
1+2+4+9+11=27이고 rejected 5,6,12,16은 더하지 않았다. - 최소성 검산: 각 accepted edge가 처리 당시 서로 다른 component를 잇는 정렬 순서상의 light/safe edge였는지 확인한다.
- 표 형식 검산: 초기 row와 남은 두 rejected row를 포함해 모든 행, \(\text{ja}/\text{nein}, =\)
ja/nein, =또는 expanded set을 빠짐없이 기록한다.
답을 가리고 하는 30초 자가점검
{a,c}:5를 선택하면 생기는 cycle을 정점 순서로 쓰라.
힌트: 이미 선택된 a-b와 b-c를 따라가 본다.
정답: a-b-c-a cycle이다. a와 c가 같은 component이므로 {a,c}는 nein이다.
{e,f}:9 행 직후 component와 누적 weight는 무엇인가?
힌트: 앞의 accepted weight 1,2,4에 9를 더한다.
정답: components는 {a,b,c,d}와 {e,f}, running weight는 \(1+2+4+9=16\)1+2+4+9=16이다.
연습: vertices p,q,r,s와 pq1, rs2, qr4, ps5를 Kruskal로 처리하라.
힌트: 처음 두 edge는 서로 떨어진 두 component를 만든다.
정답: pq1 ja, rs2 ja, qr4 ja로 모든 정점을 연결하고 ps5는 같은 component라 nein이다. MST weight는 7이다.
초보자가 자주 틀리는 지점
- 가중치만 보고 무조건 작은 간선을 고른다. 반드시 현재 component를 확인해야 한다.
- 거절된 간선 뒤에 set을 빈칸으로 둔다. 이 문제에서는 =를 포함해 모든 칸을 채워야 한다.
- union 뒤 끝점 두 개의 set만 갱신한다. 같은 component의 모든 정점 set 표현이 같아져야 한다.
- MST가 완성되자 남은 행을 쓰지 않는다. 원문은 불완전한 행을 오답 처리한다고 경고한다.
- {e,f} 행의 원문 오타 {e,ƒ}를 그대로 개념으로 받아들인다. 정점은 f다.
- 선택 간선의 총가중치를 \(1+2+4+9+11=27\)
1+2+4+9+11=27로 검산하지 않는다.
7.2 · 굵은 간선 집합이 크루스칼(Kruskal)·프림(Prim) 중 어디서 나왔는지 판별하기
문제를 한국어로 다시 읽기
각 패널의 굵은 간선 집합이 중간에 멈춘 Kruskal, 중간에 멈춘 Prim, 둘 다, 또는 어느 쪽도 아닌지 가장 정확하게 분류한다.
복기 문서의 이미지 링크에서 네 패널을 다시 확보해 사람이 공통 graph와 굵은 edge를 판독했다. 아래 SVG는 원격 이미지에 의존하지 않는 재구성이고 분류는 강의 규칙으로 검산했지만, 공식 원본·공식 답안은 아니므로 비공식 복원으로 표시한다.
소문제별 독립 개념 강의
왜 이것을 배우는가
이 문제는 최종 MST를 계산하는 문제가 아니라, 보이는 굵은 edge set이 어떤 greedy 실행의 ‘중간 사진’이 될 수 있는지 역으로 추론하는 문제다. Kruskal의 전역 정렬과 Prim의 현재 cut이라는 서로 다른 시야를 구분해야 네 패널을 정확히 분류할 수 있다.
이 소문제를 마치면: ① cut, crossing edge, light edge, safe edge를 작은 그래프에서 정의하고 cut property의 교환 직관을 설명할 수 있다. ② Kruskal의 중간 결과는 forest일 수 있지만 Prim의 중간 결과는 한 connected tree라는 차이를 사용할 수 있다. ③ 가능하다고 주장할 때 실제 edge 처리 순서 또는 Prim 시작점·cut 순서를 certificate로 제시할 수 있다. ④ 불가능하다고 주장할 때 cycle, 누락된 더 가벼운 edge, 더 싼 crossing edge 중 하나의 구체 반례를 제시할 수 있다.
풀이 전에 꼭 알아야 할 말
cut(Schnitt)과 crossing edge
cut (S,V−S)는 모든 vertex를 S와 그 밖의 V−S 두 편으로 나눈 것이다. 한 endpoint가 S, 다른 endpoint가 V−S에 있는 edge가 그 cut을 건너는 crossing edge다.
아주 작은 예: \(S=\{A,B\}\)S={A,B}라면 A-E는 crossing edge이고 A-B는 S 내부 edge라 crossing이 아니다.
light edge와 safe edge
light edge는 한 cut을 건너는 edge 중 weight가 최소인 edge다. 현재 선택 집합 A를 깨지 않는 cut의 light edge는 A를 어떤 MST로 계속 확장할 수 있게 하는 safe edge다.
아주 작은 예: crossing weights가 3,6,9라면 weight 3 edge가 light edge이고 greedy가 먼저 선택해도 안전하다.
cut property의 교환 직관
어떤 MST가 우리가 고른 light edge를 쓰지 않더라도, 그 MST가 같은 cut을 건너는 더 무겁거나 같은 edge 하나를 light edge로 바꾸면 연결과 edge 수를 유지하면서 비용이 커지지 않는다.
아주 작은 예: 기존 tree가 cut을 weight 6으로 건너면 weight 3 crossing edge로 교체해 더 비싸지 않은 spanning tree를 만든다.
Prim key와 predecessor
Prim에서 key[v]는 시작점부터 누적 거리값이 아니라 현재 tree S에서 바깥 vertex v를 붙일 수 있는 가장 싼 edge 하나의 weight다. pred[v]는 그 edge의 S 쪽 endpoint다.
아주 작은 예: 현재 S에서 G로 가는 edge가 weight 1과 6이면 \(\text{key}[G]=1\)key[G]=1이고 pred[G]는 weight 1 edge의 안쪽 정점이다.
도시 전체 구매 목록과 현재 공사 구역의 경계
Kruskal 담당자는 도시 전체 계약서를 가격순으로 펼쳐 놓고 가장 싼 안전 공사를 처리한다. Prim 담당자는 이미 전기가 들어온 한 덩어리의 공사 구역만 보고 그 경계를 넘는 가장 싼 공사를 선택한다. 같은 굵은 선 사진이라도 두 담당자의 규칙을 각각 재생해 봐야 출처를 알 수 있다.
- 도시 전체 가격순 계약서
- 크루스칼의 전체 비감소 간선 순서(global nondecreasing edge order)
- 현재 전기가 들어온 한 덩어리
- 프림의 연결된 부분 트리 S(connected partial tree)
- 구역 경계를 넘는 가장 싼 공사
- 프림 컷(cut)을 가로지르는 최소 가중치 간선(light crossing edge)
- 가능한 공사 일지
- 알고리즘 가능성을 증명하는 간선 순서 인증서(edge-order certificate)
비유의 한계: 실제 공사는 여러 계약을 동시에 할 수 있지만 두 알고리즘은 한 단계에 edge 하나를 선택하며, 문제의 굵은 집합은 그 순차 실행을 일찍 멈춘 결과다.
패널마다 적용하는 판별 필터
작은 예제로 먼저 연습 · Kruskal만 가능한 두 조각
vertices={a,b,c,d}, edges ab:1, cd:2, bc:5라고 하고 굵은 edge가 ab와 cd라고 하자.
- 순환(cycle)부터 검사
ab와 cd는 서로 떨어진 두 edge라 cycle이 없다. 따라서 Beide/하나/Keine 판정을 계속해야 한다.
이 단계 후 상태: 굵은 \(\text{forest}={\text{ab}},{\text{cd}}\)
forest={ab},{cd} - 크루스칼(Kruskal) 선택 순서를 재생
전역 weight 1의 ab와 2의 cd는 서로 다른 component를 이어 차례로 선택된다. 두 번째 선택 직후 멈출 수 있다.
이 단계 후 상태: Kruskal possible: \(\text{ab} \to \text{cd}\)
ab → cd - 프림(Prim) 선택 순서를 재생
Prim은 한 root에서 시작해 매번 새 vertex를 현재 tree에 붙인다. 떨어진 ab와 cd 두 조각을 중간 결과로 만들 수 없다.
이 단계 후 상태: Prim impossible: highlighted set disconnected
작은 예제의 결론: Kruskal은 가능하고 Prim은 불가능하므로 가장 정확한 답은 Kruskal이다. 단순히 cycle이 없다는 이유만으로 Beide라고 하면 안 된다.
실제 시험 문제로 연결하기
1. 굵은 집합이 cycle이면 왜 두 알고리즘 모두 불가능한가?
Kruskal은 같은 component를 잇는 edge를 거절하고, Prim은 매 단계 바깥의 새 vertex를 한 개 붙이므로 둘 다 accepted edge로 cycle을 만들지 않는다. 따라서 cycle 하나가 완전한 Keine certificate다.
2. disconnected이면 왜 Kruskal은 여전히 가능한가?
Kruskal은 그래프 전체에서 싼 edge를 보므로 서로 멀리 떨어진 여러 component를 동시에 키울 수 있다. 반면 Prim은 root에서 시작한 하나의 connected tree만 확장하므로 disconnected 굵은 집합은 만들 수 없다.
3. Kruskal 가능성은 어떻게 증명하나?
edge를 weight 오름차순으로 실제 나열하고, 굵은 edge는 다른 component라 accept, 빠진 더 가벼운 edge는 그 시점에 이미 같은 component라 reject됨을 보여 준다. 단순히 굵은 edge weight만 보는 것은 부족하다.
4. Prim 가능성은 어떻게 증명하나?
가능한 root를 하나 정한 뒤 현재 S, crossing candidates와 weights, 선택 edge를 단계별로 적는다. 매 단계 선택 edge가 최소 crossing weight이고 새 vertex를 붙이면 valid Prim certificate다.
5. Beide는 언제 쓰나?
같은 굵은 집합에 대해 Kruskal certificate와 Prim certificate가 모두 존재할 때만 Beide다. 한 알고리즘이 가능하다는 사실이 다른 알고리즘 가능성을 자동으로 뜻하지 않는다.
판별 규칙을 수식으로 읽기
위의 조건은 “트리 모양이다”만으로 Prim 가능성을 확정할 수 없고, 실제 선택 순서와 경계 후보를 검사해야 함을 보여 준다.
복원한 실제 네 패널과 알고리즘별 판별 근거
모든 패널은 같은 가중 그래프를 쓴다. 파란 굵은 선이 문제에서 표시된 간선(edge), 회색 점선이 미표시 간선이며, 순환(cycle) 반례는 빨간색으로 강조했다. 각 판정은 Kruskal과 Prim을 따로 실행해 확인한 결과다.
왼쪽 위 · Beide
굵은 edge는 connected acyclic tree이며 Kruskal의 global order와 Prim의 cut-minimum order를 모두 재생할 수 있다.
크루스칼 알고리즘(Kruskal) · 가능
- AB1과 GH1은 tie 순서 중 \(\text{AB}\to \text{GH}\)
AB→GH로 각각 다른 singleton을 이어 선택한다. - AE3은 {A,B}와 E를, DF4는 D와 F를 이어 선택한다.
- EF5는 {A,B,E}와 {D,F}를 합치고 FH5는 그 component와 {G,H}를 합친다.
- 선택 순서 \(\text{AB}1\to \text{GH}1\to \text{AE}3\to \text{DF}4\to \text{EF}5\to \text{FH}5\)
AB1→GH1→AE3→DF4→EF5→FH5직후 멈추면 굵은 집합과 같다.
프림 알고리즘(Prim) · 가능
가능한 시작점: B
- S={B}: crossing AB1,BD12 중 AB1 선택.
- S={A,B}: crossing AE3,AD6,AG9,BD12 중 AE3 선택.
- S={A,B,E}: crossing EF5,AD6,EG6,CE7,AG9,DE10,BD12 중 EF5 선택.
- S={A,B,E,F}: crossing DF4,FH5,AD6,EG6,CE7,AG9,DE10,BD12 중 DF4 선택.
- S={A,B,D,E,F}: crossing FH5,EG6,CE7,AG9 중 FH5 선택.
- S={A,B,D,E,F,H}: crossing GH1,EG6,CE7,AG9 중 GH1 선택 후 조기 종료.
오른쪽 위 · Kruskal
전역에서 가장 가벼운 네 edge를 Kruskal이 선택한 disconnected forest다. Prim은 한 connected tree만 만들므로 불가능하다.
크루스칼 알고리즘(Kruskal) · 가능
- weight 1의 AB와 GH는 서로 다른 singleton을 이어 둘 다 선택한다.
- 다음 AE3은 {A,B}와 E를 연결하고 DF4는 D와 F를 연결한다.
- \(\text{AB}1\to \text{GH}1\to \text{AE}3\to \text{DF}4\)
AB1→GH1→AE3→DF4뒤 실행을 멈추면 정확히 네 굵은 edge가 남는다. - 굵은 결과는 {A,B,E}, {D,F}, {G,H}, {C}의 forest다.
프림 알고리즘(Prim) · 불가능
가능한 시작점: 없음
- Prim은 root 하나에서 시작해 매 accepted edge로 바깥 vertex 하나를 붙인다.
- 따라서 edge가 하나 이상인 모든 중간 결과가 connected tree다.
- 이 패널은 {A,B,E}, {D,F}, {G,H}가 서로 떨어져 있어 어떤 root로도 만들 수 없다.
- disconnected라는 한 가지 반례만으로 Prim 가능성을 배제할 수 있다.
결정적 근거: highlighted set이 세 개의 nontrivial component로 분리되어 있다.
왼쪽 아래 · Keine
굵은 AD,DF,FE,EA가 A-D-F-E-A cycle을 만든다. 두 알고리즘의 accepted 중간 결과는 모두 acyclic이므로 즉시 Keine다.
크루스칼 알고리즘(Kruskal) · 불가능
- AB1,GH1,AE3,DF4,EF5를 처리하면 A,B,D,E,F가 이미 한 component다.
- 같은 weight 5의 FH도 가능하지만, AD6 시점에는 A와 D가 이미 A-E-F-D path로 연결되어 있다.
- Kruskal은 AD6을 cycle edge로 반드시 거절해야 한다.
- 굵은 집합이 AD6을 포함하므로 valid Kruskal prefix가 아니다.
결정적 근거: A-E-F-D-A cycle 때문에 AD6은 accept될 수 없다.
프림 알고리즘(Prim) · 불가능
가능한 시작점: 없음
- Prim은 매 단계 현재 tree 밖의 새 vertex를 하나 붙인다.
- 따라서 accepted edge 수를 하나 늘릴 때 cycle을 만들 수 없다.
- 굵은 집합에는 A-D-F-E-A closed path가 이미 있다.
- 어떤 root와 tie order를 택해도 이 cycle 전체가 Prim 중간 tree가 될 수 없다.
결정적 근거: highlighted AD,DF,EF,AE가 cycle을 이룬다.
오른쪽 아래 · Keine
모양은 connected tree지만 GH1을 누락했다. Kruskal은 GH1을 초기에 반드시 고르고, Prim도 H 또는 G가 tree에 들어오는 순간 GH1이 cut-minimum이라 EG6보다 먼저 강제된다.
크루스칼 알고리즘(Kruskal) · 불가능
- global order의 최소 weight는 AB1과 GH1이다.
- GH1을 처리할 때 G와 H는 아직 서로 다른 singleton이므로 cycle로 거절할 수 없다.
- 따라서 Kruskal은 GH1을 반드시 선택해야 한다.
- 굵은 집합에는 GH가 없으므로 이후 EF5,FH5,EG6을 포함한 prefix와 일치할 수 없다.
결정적 근거: 누락된 GH1은 처리 당시 safe하며 반드시 accepted된다.
프림 알고리즘(Prim) · 불가능
가능한 시작점: 어느 root도 불가
- G 또는 H에서 시작하면 crossing minimum GH1이 첫 edge로 즉시 강제된다.
- C에서 시작하면 유일한 crossing edge CE7이 첫 edge로 강제되지만 굵은 집합에는 CE가 없다.
- A,B,D,E,F 쪽에서 시작해 굵은 tree를 만들면 EG6 전에 EF5와 FH5를 통해 H가 tree에 들어온다.
- H가 안쪽이고 G가 바깥인 cut에서 GH1은 EG6보다 싼 crossing edge다.
- 따라서 GH1을 건너뛰고 EG6을 선택하는 Prim 순서는 존재하지 않는다.
결정적 근거: FH로 H를 포함한 뒤에는 GH1이 cut-minimum이므로 EG6보다 먼저 선택돼야 한다.
어떤 그림도 판별하는 5단계
1단계 · 굵은 간선 자체가 cycle을 만드는가?
Kruskal과 Prim의 모든 중간 결과는 cycle이 없는 forest다. 굵은 간선만으로 cycle이 있으면 즉시 Keine다. 이 검사는 가장 빠른 탈락 조건이다.
2단계 · 굵은 간선이 연결되어 있는가?
Prim은 시작 정점 하나에서 tree를 한 간선씩 확장하므로, 간선이 하나 이상인 모든 중간 결과가 connected다. 굵은 간선들이 서로 떨어진 두 component라면 Prim은 불가능하다. Kruskal은 forest를 만들 수 있으므로 아직 가능하다.
3단계 · Kruskal의 전역 가중치 순서를 역으로 검사
굵지 않은 더 가벼운 간선 e가 있는데, e를 처리했을 당시 그 양 끝이 굵은 더 가벼운 간선들만으로 연결되지 않았다면 Kruskal은 e를 반드시 선택했어야 한다. 그러므로 그 상황에서 e가 빠져 있으면 Kruskal 불가능이다. 동률이면 tie order가 존재하는지도 함께 본다.
4단계 · Prim의 cut 선택 순서를 역으로 검사
어떤 시작 정점과 굵은 간선 순서를 잡아, 매 단계 현재 tree S에서 바깥 V−S로 나가는 최소 가중치 edge를 하나씩 고를 수 있는지 찾는다. 한 단계라도 더 싼 crossing edge를 건너뛰고 비싼 굵은 edge를 골라야 하면 Prim 불가능이다.
5단계 · 가능성 두 개를 조합
Kruskal 가능·Prim 가능이면 Beide, Kruskal만 가능이면 Kruskal, Prim만 가능이면 Prim, 둘 다 불가능이면 Keine다. 둘 다 가능할 때 하나만 쓰면 '가장 정확한 답' 요구를 위반한다.
크루스칼(Kruskal)과 프림(Prim)을 한눈에 비교
| 기준 | 크루스칼(Kruskal) | 프림(Prim) |
|---|---|---|
| 선택 후보 | 그래프 전체의 미처리 간선 | 현재 tree와 바깥을 잇는 crossing edge |
| 중간 모양 | 여러 component인 forest 가능 | 항상 하나의 connected tree |
| 항목 (cycle) | 금지 | 새 정점을 붙이므로 금지 |
| 시작점 | 없음 | 필요하며 어느 시작점이 가능한지 탐색 |
| 자료구조 | 정렬 + Union-Find | priority queue + key/predecessor |
네 정답 유형별 독립 훈련
아래는 원본 네 패널의 정답이 아니라 판별 규칙을 익히는 예시다.
크루스칼만 가능(Kruskal)
훈련 상황: 굵은 간선이 {a,b}(1)과 {d,e}(2)처럼 서로 떨어져 있고, 이 둘이 전역적으로 가장 가벼운 안전 간선이라고 하자.
판정 이유: Kruskal은 두 component를 따로 만들 수 있다. Prim 중간 결과는 하나의 connected tree여야 하므로 불가능하다.
프림만 가능(Prim)
훈련 상황: 굵은 간선이 시작점 a에서 연결된 tree를 이루지만, 다른 곳에 더 가벼운 독립 간선 {x,y}가 빠져 있다고 하자. 대신 매 단계 a-tree의 cut에서 선택한 간선은 최소라고 하자.
판정 이유: Prim은 tree 바깥 내부의 {x,y}를 볼 필요가 없어 가능하다. Kruskal은 전역적으로 더 가벼운 안전 간선을 먼저 처리하므로 {x,y}를 빼고 진행할 수 없다.
둘 다 가능(Beide)
훈련 상황: 굵은 간선들이 connected tree를 이루고, 가중치 순으로도 각각 당시 cycle을 만들지 않는 가장 가벼운 간선이며, 어떤 시작점에서 cut-minimum 순서로도 추가할 수 있다고 하자.
판정 이유: 두 알고리즘의 서로 다른 선택 규칙을 모두 만족한다. 가장 정확한 답은 Kruskal이나 Prim 하나가 아니라 Beide다.
둘 다 불가능(Keine)
훈련 상황: 굵은 간선들이 triangle cycle을 만들거나, Prim이 더 싼 crossing edge를 건너뛰어야 하고 Kruskal도 더 싼 안전 간선을 누락해야 한다고 하자.
판정 이유: cycle 하나만 있어도 둘 다 즉시 불가능하다. cycle이 없어도 두 알고리즘의 greedy 조건을 모두 위반하면 Keine다.
헷갈리는 논리를 끝까지 풀어보기
- 이 문제는 최종 MST가 맞는지 묻는 문제가 아니다. '중간에 일찍 멈춘 실행'도 허용하므로 굵은 간선이 모든 정점을 연결할 필요도 없고 |V|-1개일 필요도 없다.
- Prim 판별에서 connected는 필요조건이지만 충분조건은 아니다. 연결된 tree처럼 보여도 매 단계 더 싼 crossing edge를 무시해야 한다면 Prim 실행으로 만들 수 없다.
- Kruskal 판별에서 가중치가 작은 굵은 간선들만 보는 것으로는 부족하다. 빠진 얇은 간선이 그 시점에 cycle 때문에 거절될 수 있었는지 확인해야 한다.
- 동일 가중치가 있으면 정답 가능성이 넓어진다. 강의나 문제에서 tie-breaking 순서를 지정하지 않았다면, 같은 가중치 간선들 중 굵은 집합을 만들어 주는 처리 순서가 하나라도 존재하는지를 본다.
- 완성된 MST는 connected이므로 모양만 보면 Prim 같지만, 어떤 MST라도 특정 tie/order 아래 Kruskal과 Prim 둘 다 만들 수 있는지는 그래프의 가중치 구조를 검증해야 한다. 외형만으로 Beide라고 쓰면 안 된다.
시험장에서 그대로 쓰는 판별 템플릿
각 그림마다 (1) cycle이면 Keine, (2) disconnected면 Prim 제외, (3) Kruskal은 빠진 더 가벼운 간선이 당시 cycle로 거절 가능했는지 확인, (4) Prim은 가능한 시작점과 순서를 잡아 매 단계 cut-minimum인지 확인한다. 두 가능성을 조합해 Kruskal/Prim/Beide/Keine 중 가장 정확한 하나를 쓴다.
풀이 후 검산
- 각 패널에서 굵은 edge의 cycle과 connected component 수를 먼저 손으로 확인한다.
- Kruskal possible에는 nondecreasing 처리 순서를, impossible에는 반드시 포함돼야 할 누락 edge 또는 순서 위반을 적는다.
- Prim possible에는 root·cut-minimum 순서를, impossible에는 disconnected 또는 더 싼 crossing edge를 적는다.
- 최종 label이 두 가능성의 조합과 일치하는지 확인한다: \(\text{TT}=\text{Beide}, \text{TF}=\text{Kruskal}, \text{FT}=\text{Prim}, \text{FF}=\text{Keine}.\)
TT=Beide, TF=Kruskal, FT=Prim, FF=Keine.
답을 가리고 하는 30초 자가점검
connected이고 cycle이 없는 굵은 tree면 무조건 Prim 가능한가?
힌트: 모양뿐 아니라 매 단계 crossing edge의 weight를 본다.
정답: 아니다. 어떤 순서에서도 더 싼 crossing edge를 건너뛰어야 한다면 Prim은 불가능하다.
disconnected 굵은 forest가 Keine가 아닌 이유는?
힌트: 두 알고리즘 중 여러 조각을 동시에 키울 수 있는 쪽을 생각한다.
정답: Kruskal은 전역에서 edge를 처리하므로 여러 component인 중간 forest를 만들 수 있다.
연습: 굵은 edge가 triangle 세 변이면 답은 무엇인가?
힌트: 가장 먼저 cycle 필터를 적용한다.
정답: Keine다. Kruskal과 Prim 모두 accepted edge 중간 결과에 cycle을 만들 수 없다.
초보자가 자주 틀리는 지점
- 굵은 간선이 connected이면 곧바로 Prim이라고 한다. cut-minimum 조건도 필요하다.
- 굵은 간선이 disconnected이면 Keine라고 한다. Kruskal의 중간 forest일 수 있다.
- 최종 spanning tree가 아니므로 둘 다 아니라고 한다. 문제는 조기 종료를 명시적으로 허용한다.
- Kruskal이 현재 component와 맞닿은 간선만 본다고 착각한다. 그것은 Prim 쪽 사고방식이다.
- Prim이 그래프 전체의 최솟값을 반드시 고른다고 착각한다. 현재 cut을 가로지르는 간선 중 최솟값만 고른다.
- 둘 다 가능하지만 Kruskal 또는 Prim 하나만 적는다. 원문은 Beide를 요구한다.
- 네 패널이면 Kruskal·Prim·Beide·Keine가 반드시 한 번씩 나온다고 가정한다. 실제 복원 패널은 Beide, Kruskal, Keine, Keine이며 Prim-only 패널이 없다.
근거와 정확성 범위
복기 문언, 강의 정의, 공식 연습 풀이, 추가 유도를 구분해 표시합니다.
- 복기 시험 문언
AuD Gedächtnisprotokoll SoSe 2025.md· lines 297-319 · 신뢰도/범위: 비공식 복기이며 공식 문제지·공식 답안 아님7.1 간선표와 정답 행, 7.2 문제 문언 및 조기 종료 허용
- 강의 직접 근거
Vorlesung\06GraphAlgorithms.pdf· pp.82-90 (MST·cut), pp.92-106 (Kruskal), pp.107-117 (Prim) · 신뢰도/범위: 현재 강의 자료MST 정의, 두 greedy 알고리즘과 정확성 근거
- 공식 연습 풀이
Übung\AuD26_Sheet10-Sol.pdf· pp.1-5 and pp.13-14 · 신뢰도/범위: 공식 연습 풀이현재 강의의 Prim/Kruskal 표 작성 방식과 상세 실행 설명
- 공식 연습 문제
Übung\AuD26_Sheet10.pdf· G2-G3 · 신뢰도/범위: 공식 연습 문제Prim과 Kruskal 손실행 연습 형식