最小树形图
2026-08-25
定义
一张有向图的最小生成树称为最小树形图。
朱刘算法
求解这个问题的一种算法是朱刘算法,一种类似于贪心的解法。
对于原图中的每个点,我们保留其边权最小的入边:
- 若新的图中没有环,则显然新图为原图的最小树形图。
- 若新的图中有环,由于每个点的入度为 1,所有环必定不相交,将原图缩点,得到新图 G′,对于其中的每条边:
- 若其在环内部,直接删去。
- 若其终点在环上,则将其边权减去终点在环内入边权。
- 其他的边,权值不变。
在缩点过程中,最优解有一些性质:
- 每个环至少去掉一个边。
- 必然存在一个最优解,只需要去掉一条边。
证明:由于删去一个边一定需要为它再找一个新的入边,而新的入边一定不小于删去的边,所以不会更优。
