对Kruskal算法的一些理解&各种MST

首先我们来回顾一下Kruskal的基本思想和原理　　第一次发文，好激动

原理

我们每次先把边按照权值大小进行排序，然后我们从小到大开始进行选择，每次判断边的两个端点所在的连通块是否相同，不同则将它选入MST并继续向下考虑

理解

通过上面的过程我们可以获得一些好的思路，比如边的选取只是与它在边的序列中的排名有关系，而与其他的因素无关。这样我们完全可以在大部分时候无视除最小生成树边以外的其他边，只留下n-1条最小生成树边，这样对于所有对边进行的操作(如删除或增边)，如果不在这一段区间中则可以忽略，否则我们就只需要对这个区间进行修改与调整。这样大大地简化了我们的思维复杂度

各种各样的MST

这些东西应该都是老生常谈了，在刘汝佳蓝书上应该已经快被翻烂了，但本文还是将它们拿出来说一说

最小生成树

最普通的一种，就不再赘述了

最小瓶颈生成树

可以从字面上来理解，它就是指这一棵生成树上，所有树边权值的最大值最小的那一棵树(MST)。通过上面的“理解”我们可以很容易知道所有的最小生成树都一定是最小瓶颈生成树，反之并不一定

最小瓶颈路

这个东西指的是一条从u到v的路径，这条路径它满足其经过的所有边中权值的最大值最小（其中u和v都是给定的）。它的求法仍与最小生成树有关。我们可以先求出原图的最小生成树，然后在这棵树上寻找u和v的树上路径，那么这条路径即为所求。这样做为什么是对的呢？我们可以用上文所述的“理解”来进行证明（如采用反证法），这里不再赘述。由此我们也能看到Kruskal带给我们的理解是多么地重要

每对节点间最小瓶颈路

这其实就是对上面内容的一个小扩展。刘汝佳给出了一个时间复杂度为O( n2 )的算法，要是不满意这样的复杂度，也可以用点分治来优化啊，反正我是不满意。当然如果需要把所有点对间的最小瓶颈路都求出来，刘汝佳的复杂度已经是下界了

次小生成树

说到“次小”这个前缀，我不得不想起“K小”基于上一个内容，我们可以先用O( n2 )的复杂度把任意两点间的瓶颈路求出来，然后就是枚举树边之外的所有边，再用预处理后的瓶颈路搞一搞就行了

最小有向生成树（树形图）

为了这个树形图，我们回顾一下朱刘算法。首先我们可以判定一下解的存在性，若存在则继续。我们每次先找到所有当前点的权值最小入边（即指向这个点的有向边），然后考虑这些边是否形成圈（环），若有环则缩点，重复上述过程直到没有环存在，最后再将每个环展开，除去环中多余的边，最后的边形成了原图的树形图

严格次小生成树

（2017.2.17更新）不知不觉做到这样一道题，让你求出一个无向图的严格次小生成树。什么是严格次小生成树呢，那就是它的权值要严格小于最小生成树。而普通次小生成树则无需如此（就像上文所说的那样）。这种生成树也非常简单，我们只要先预处理出每两个点的“次小瓶颈路”即可，一种包含了两点之间最长路以及严格次小路权值的数组。这样，我们每次对非树边进行枚举，将它加入到原树中，并对形成的那个环进行修改，如果环上的最长路与新加入的边长度相同，则考虑它的次小路边长（当然要是不存在直接跳过就行），最后得到的最大的那个严格次小生成树权值就是答案。那么，为什么那样做是对的呢？我们可以再次回归到理解上，如果一条边加入原树后，它处理完成以后总权值不变，那么无论别的边怎么替换，它这条边一定是毫无意义的，可以说它与原来被它替换的那条树边等价，这一点应该很好理解

瓶颈路的求法

暴力法

即上文中提到的求出任意两点的瓶颈路，在一次DFS中即可求出，复杂度为 O(n2)

倍增+LCA

上文中提到了瓶颈路的求法是吧？现在回想一下，上面的方法在今天着实是不大适用了。对我们来说，我们其实并不需要一开始就把所有的两点间的瓶颈路求出来，我们完全可以考虑采用LCA，并使用倍增法进行实现，把时间复杂度优化到 O(nlogn) 。具体并不困难。当然瓶颈路这种说法其实本身就是多余的，完全可以在倍增求LCA的同时保存我们想要的信息，再 O(logn) 查询即可

模板

说实话现在本文最缺的就是模板了，然而我也懒得写，此处留坑待补

总结

我们在这里大致地探讨了MST的相关内容，对于例题及习题将由其他的博文进行探讨与总结