最小生成树

Theoretical Foundation

引理：在多个点的最小生成树中，最短边一定是树边。

证明：反证法。假设最短边不是树边，那么把最短边加入最小生成树肯定会形成一个环，此时将环中的另一条边去掉，仍然是树，但是总权值减小了，矛盾。所以最短边肯定是树边。

Prim算法和Kruskal算法都是基于这个引理的。

Kruskal算法

算法非常朴素。我们最开始将所有边进行排序。每一次加边，我们都要对点维护一个并查集，我们从小到大找边，加入第一个 两个端点不在同一个集合 的边。

这个算法的本质思想是缩点，每一个集合我们看成一个点，重新构造最小生成树，那么我们这个算法加入的边就是这个生成树的最短边，根据引理必定是树边。

Prim算法

这个算法很像dijkstra。开始先加入一号点，每一次我们选择的边是两个端点为已经加入的点和没有加入的点的边中最短的边。

这个算法的本质也是缩点。这时我们将已经选择的所有点缩成一个点，因为内部不可能再加入任何边了。我们同时将没有选择的点也所缩成一个点，里面我们会加入边，但是我们现在先将其抽象掉（或假设里面的边已经全部连接好了），不考虑他们。因为我们急切需要一条边来连接这两个缩点，否则不构成连通图，所以此时我们是在构建两个点的最小生成树，也就是选择最短边。

Final thoughts

通过引理推出这两个算法的本质是很令人愉快的一件事。只知道算法如何运行，直觉上认为正确也是很重要的，但是只有脚踏实地的证明才感觉完整。