Question

图的最小生成树算法(Prim和Kruskal)

Answer 1

图的邻接矩阵表示法可参考： https://www.jianshu.com/p/9f27288f6749
测试图如图所示：

思想：先选取一个顶点加入最小生成树，再选取与该顶点相连的边中的最小权值对应的顶点加入生成树，将这两个顶点作为一棵新的最小生成树，继续判断与该树相连的边的最小权值对应的顶点，并将其加入最小生成树，直到所有顶点均加入生成树为止。

测试程序

测试结果：

思想：将图的存储结构使用边集数组的形式表示，并将边集数组按权值从小到大排序，遍历边集数组，每次选取一条边并判断是否构成环路，不会构成环路则将其加入最小生成树，最终只会包含n-1条边(n为无向图的顶点数)。

边集数组的结构如图所示：

测试程序：

测试结果：

最小生成树为：

普里姆算法针对顶点展开，通过不断寻找与已构建的生成树的最小边来不断构建新的生成树。普里姆算法对于稠密图，也就是边数非常多的情况会更好一些，因为其是通过顶点来展开的。算法时间损耗主要来源于嵌套的for循环，所以时间复杂度为O(n^2)。

克鲁斯卡尔算法针对边展开，通过对边集数组的遍历来构建最小生成树，但是过程中必须避免构成环路。克鲁斯卡尔算法对于稀疏图，也就是边数较少的情况效率会很高。此算法的Find函数由边数e决定，时间复杂度为O(loge)，再加上外层for循环的e次，所以时间复杂度为O(eloge)。