最小生成树总结

Prim算法

prim算法是主要解决与边数无关和顶点数相关的算法，适合求解稠密图的最小生成树。

算法的时间复杂度为$O(n^2)$，空间复杂度是$O(n^2)$。

步骤 1.从任意一个顶点开始构造生成树，用一个数组记录哪些顶点已经加入了生成树。 2.用数组dist记录生成树到各顶点的距离。 3.从数组dist中选出离生成树最近的顶点（假设为j）加入到生成树中。再以j为中间点，更新生成树到每一个非树顶点的距离（松弛）。 4.重复第三步，直到生成树有n个顶点为止。

book[1] = 1; count++; while (count < n) { min = inf; for (i = 1; i <= n; i++) { if (!book[i] && dis[i] < min) { min = dis[i]; j = i; } } book[j] = 1; count++; sum += dis[j]; for (k = 1; k <= n; k++) { if (!book[k] && dis[k] > e[j][k]) dis[k] = e[j][k]; } }

Kruskal算法

Kruskal算法是经典的最小生成树算法，用于计算将顶点连通的最小权值。

适合解决点多边少的稀疏图，算法的时间复杂度是$O(M\log M)$，空间复杂度为$O(M)$。

步骤： 1.对所有的边按照权值进行小到大的排序。 2.然后每次选取最小的权值，如果和已有点集构成环则跳过，否则加入生成树，直到选择了n-1条边。

for (i = 1; i <= m; i++) { if (merge(e[i].u, e[i].v)) { counts++; sum += e[i].w; } if (counts == n - 1) break; }