02JUL
JUL 02
今天的关键词
最小生成树
Cut 定理
Prim
02记录天数
20知识点
02待研究题目
成长不是把页面填满，
而是让一个想法真正变清楚。
LEARNING TIMELINE
这两天，我们走到了这里
从“为什么贪心是对的”，走到“怎样用最便宜的边连接所有点”。
01JUL
2026 / 07
02
星期四
TODAY'S NOTE · 图论
最小生成树：
从选边，到长出一棵树
今天不是多记一个模板，而是找到 Prim 和 Kruskal 背后共同的理由。
已经会了
Kruskal
把边按权值排序，不断选择不会成环的最短边。
今天想清楚
Cut 定理
把点分成两边，跨过分界线的最便宜边是安全选择。
接下来掌握
Prim
从一个点出发，每次接入距离当前树最近的新点。
FOUNDATION · 基础地图
先把“最小生成树”说准确
算法模板之前，先分清图、树、生成树与最小生成树。
使用条件
研究对象通常是一个带权、无向、连通图。如果原图不连通，就不存在覆盖所有顶点的生成树。
什么是生成树
包含原图全部顶点、保持连通且没有环。若有 n 个顶点，生成树一定恰好有 n − 1 条边。
“最小”在哪里
比较的是整棵生成树的边权总和，不是让每一条边都分别最小，也不是求两个点之间的最短路。
答案可能不唯一
不同的生成树可能拥有相同的最小总权值。因此“最小生成树”不一定只有一棵，但最小权值相同。
CUT PROPERTY · 正确性核心
Cut 定理不只是口诀，
它解释了为什么可以贪心。
- Cut（割）
- 把所有顶点分成两个非空集合。
- 跨割边
- 两个端点分别位于 Cut 两侧的边。
- 轻边
- 所有跨割边中权值最小的边。
- 安全边
- 加入当前选择后，仍然能够扩展成某棵最小生成树的边。
交换证明 · 5 步
- 1
取一棵最小生成树 T，假设它没有选择轻边 e。
- 2
把 e 加入 T，树中会出现一个环。
- 3
这个环上一定还有一条跨过同一 Cut 的边 f。
- 4
因为 e 是轻边，所以 w(e) ≤ w(f)。
- 5
删掉 f，仍是生成树且总权值不会变大。
所以：一定存在一棵最小生成树包含轻边 e。
若轻边唯一，它属于所有最小生成树；若有并列轻边，只能保证任选一条可以进入某棵最小生成树。
01
核心概念
给孩子讲 Cut 定理
画一条线，把村庄分成左右两边。反正两边最终必须连起来，那就可以放心选择最便宜的跨线道路。
A
B
已经连好的村庄
CUT
C
D
还没连进来的村庄
画条线，分两边；要连通，必跨线；跨线道路选最短，放心加入不会亏。
02
方法对照
Kruskal 与 Prim
比较KruskalPrim
视角全图选边从树向外扩展
核心工具排序 + 并查集dis + vis
更适合稀疏图稠密图
Prim 最容易和 Dijkstra 混淆的地方：
// Prim：连接到当前树的边
dis[v] = min(dis[v], w);
// Dijkstra：从起点走到 v 的路
dis[v] = min(dis[v], dis[u] + w);
03
PRIM · 算法流程
让一棵树从一个点慢慢长大
- 初始化
任选起点，例如 1 号点。令
dis[1] = 0，其余为无穷大。 - 找最近点
在尚未加入生成树的点中，找到
dis最小的点u。 - 加入答案
标记
vis[u] = true，并把dis[u]加入生成树总权值。 - 更新距离
枚举
u的出边，用边权更新其他点：dis[v] = min(dis[v], w)。 - 检查连通
如果某轮找不到有限距离的新点，说明原图不连通，不存在最小生成树。
BORŮVKA · 第三种经典算法
思想一听就懂，
实现需要再跨一步。
当前状态
懂思想 · 不会实现
这是非常正常的学习阶段
每一轮，让每个连通块同时选择一条通向外部的最便宜边，再用并查集合并；不断重复，直到只剩一个连通块。
找到连通块
最开始每个点各自是一个连通块，以后由并查集维护。
寻找最便宜出边
扫描所有边，为每个连通块记录一条连接到外部的最小边。
统一合并
再次检查端点是否已经连通；若没有，就加入答案并执行 union。
进入下一轮
连通块数量至少大幅减少，重复约 log n 轮后完成。
为什么正确？
每个连通块都天然形成一个 Cut。
把这个连通块放在 Cut 一侧，其余顶点放在另一侧。它选择的最便宜出边就是跨过这个 Cut 的轻边，因此根据 Cut 定理，这条边是安全边。
代码真正难在哪里？
- 每轮都要清空并重新记录各连通块的最便宜出边。
- 一条边可能同时成为两个连通块的选择，不能重复计入。
- 前面的合并会改变连通关系，加入边前必须再次 find。
- 需要统计合并次数，判断已经连通还是原图不连通。
推荐学习顺序
Kruskal 与并查集熟练→
手动模拟 Borůvka→
理解每块的 cheapest[]→
最后独立实现
WATCH OUT · 易错点
会写模板之前，先避开这些坑
- 把 Prim 当成 Dijkstra：Prim 更新边权
w，不是路径长度dis[u] + w。 - 忘记无向边：邻接矩阵或邻接表需要同时加入
u → v和v → u。 - 重边直接覆盖：两个点之间有多条边时，应保留权值最小的一条。
- 没有判断不连通：最小的未访问点仍是无穷大时，应报告不存在生成树。
- 误解 Cut 定理：并列最小边不一定全部出现在同一棵最小生成树中。
QUICK CHECK
三问，看看是否真的明白
先在心里回答，再点开答案。
Cut 定理里的“Cut”到底是什么？
把所有顶点分成两个非空集合。端点分别落在两边的边，就是跨过这个 Cut 的边。
跨过 Cut 的最小边一定属于所有最小生成树吗？
不一定。它一定可以出现在某棵最小生成树中；只有当最小边唯一时，才能说它出现在所有最小生成树中。
Prim 的 dis[v] 表示什么？
点 v 通过一条边连接到“当前生成树”的最小代价，不是起点到 v 的路径长度。
一棵生成树为什么一定有 n − 1 条边？
树既连通又无环。从一个点开始，每加入一个新点恰好需要一条边，因此连接 n 个点需要 n − 1 条边。
Prim 从不同起点出发，答案会变吗？
最小总权值不会变，但当最小生成树不唯一时，最终选出的具体边集合可能不同。
Borůvka 为什么每一轮都要重新寻找最便宜出边？
合并后连通块已经改变。上一轮的出边可能变成连通块内部的边，因此必须根据新的连通块重新扫描和选择。
PARKING LOT · 暂存区
两道题，先放在这里
还没有正式研究，所以现在只收好题目、标记来源，不提前写思路和答案。等真正开始做时，再把过程补回来。
2026 / 07
01
星期三
YESTERDAY'S NOTE · 贪心
交换一下，
为什么不会更差？
第一次认真面对贪心证明：不是“它看起来最好”，而是说明它一定可以通向最优解。
1
→
拿一个最优解
先承认答案就在那里。
2
→
做一次交换
把它改得更像贪心选择。
3
证明不会更差
最优性没有被交换破坏。
GREEDY FOUNDATION · 基础
贪心算法到底在“贪”什么？
每一步做一个眼前最合适且不可撤销的选择，希望这些局部选择最终构成全局最优解。
贪心选择
当前只根据已经看到的信息做决定，不枚举所有完整方案，也通常不会回头修改。
安全策略
需要证明：至少存在一个最优解与这次贪心选择一致。看起来合理还不够。
最优子结构
做完一次安全选择后，剩余部分仍然是同类问题的一个更小实例。
举例不是证明
样例只能说明算法在几个输入上成功；证明必须覆盖所有满足条件的输入。
区间调度
结束得越早，给后面留下的空间越多。
按结束时间排序- 目标：选择最多个互不重叠区间
- 安全选择：当前可选区间中结束最早者
- 交换理由：替换最优解第一个区间后，不会挤占更多后续空间
最大迟到时间
截止时间早的任务，不应该被晚截止的任务挡在后面。
EDF：早截止先做- 目标：让所有任务中的最大迟到量最小
- 逆序：前面任务截止时间反而更晚
- 交换理由：消除相邻逆序不会增大最大迟到量
奶牛玩杂技
比较相邻两头奶牛交换前后的最坏风险。
按 w + s 排序- 目标：最小化最大的压扁指数
- 只比较相邻两头奶牛的两种顺序
- 交换理由：错误顺序调整后，其他奶牛受到的重量不变
PROOF WORKSHOP · 证明工具箱
交换论证的完整写法
- 选择对象
设贪心算法当前选择的是 G，再任取一个最优解 S。
- 处理一致情况
如果 S 已经选择了 G，这一步天然安全，可以继续研究剩余问题。
- 找到可交换对象
如果不一致，在 S 中找到与 G 对应的对象 X。
- 执行替换
用 G 替换 X，得到新方案 S′。
- 证明两件事
S′ 仍然合法，并且目标值不比 S 更差。
- 推进到完整方案
不断交换，最终把某个最优解变成与贪心算法完全一致的方案。
COMMON ERRORS · 常见错误
证明最容易缺的五句话
- 只描述了算法，没有证明为什么正确。
- 只说“这样最好”，没有构造交换后的方案。
- 只比较被交换的一个对象，忘了检查另一个对象。
- 没有说明交换后其他对象为什么不受影响。
- 证明了一次交换，却没说明如何重复到完整贪心顺序。
NEW PROBLEM · 遇到新题
寻找贪心规则的顺序
- 先把目标函数说清楚：最大什么，或最小什么？
- 列出几个自然策略：最早、最短、最大、最小、比值排序。
- 主动构造反例，尽早淘汰错误策略。
- 观察最优解和候选策略第一次不同的位置。
- 尝试局部交换，并检查合法性与目标值。
LEARNING KIT
昨天留下的完整学习包
讲义负责把话说清楚，互动课堂负责亲手试一试，综合训练负责检查是否真的会了。
ABOUT THIS LOG
这不是成绩单，
是一张思考生长的地图。
每条记录只回答三件事：今天弄懂了什么、还在哪里卡住、下一步准备往哪里走。
“待研究”不是空白，而是给未来的自己留下一个清楚的入口。