图优化算法
引入
词汇
| English | 释义 | 拼音 |
|---|---|---|
| cuts | 割 | gē |
| Kruskal | 克鲁斯卡尔 | kè lǔ sī kǎ ěr |
跨割的轻边
- 割 cuts 把顶点分成两侧；跨割最轻的边可以安全接受——这是 Kruskal（排序、接受、拒环）与 Dijkstra 安定步的共同根基。
{exercise:uni-cs1005-cut}
练习
跨割最轻的边——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
生成树加轻边减环上另一边，权不变或更小。
课程图上的 Kruskal
- 排序后：C–B 1、A–C 2、D–E 2、E–F 3、A–B 4、B–D 5、D–F 6、C–D 8、C–E 10。接受 C–B、A–C、D–E、E–F、B–D；其余成环拒绝。
- MST 权 $1+2+2+3+5 = 13$，套件已验证。证明：任一生成树加轻跨割边、去环上另一跨割边，权不变或更小。
{exercise:uni-cs1005-kruskal}
练习
课程图上 Kruskal 的 MST 权为——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
CB 1 + AC 2 + DE 2 + EF 3 + BD 5 = 13。
负权边
- Dijkstra 安定即不再回头：A→B (5)、A→C (1)、C→B (1) 上，把 B 安定在 5 就漏掉权 2 的路径。
- 轻边保证需要非负权；有负权时 Bellman-Ford 的 $\Theta(VE)$ 轮松弛才是诚实的工具——它还能发现负环。
{exercise:uni-cs1005-negative}
练习
边 A-B 5、A-C 1、C-B 1 上，就近安定的 Dijkstra 把 B 定为——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
B 在 C 松弛它之前安定：5——漏掉经 C 的 2；应改用 Bellman-Ford。