最小生成树算法总结

Kruskal算法

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

最常见的问题就是：已知N座城市中任意两座城市之间建造道路所需要的费用，求最少花费多少就可以使得任意两座城市都可以通过所建造的道路互相到达。

算法核心：首先选择最短的边，然后选择次短的边……直到选择n-1条边为止。算法的时间复杂度为O(MlogM)，空间复杂度为O(M)。

基本步骤如下：

  1. 对所有的边按照权值进行从小到大排序。
  2. 然后每次选取最小的权值，如果和已有点集构成环则跳过，否则加到该点集中，直到选择了n-1条边让整个图连通为止。最终由所有的点集构成的树就是最佳的。

Kruskal算法核心代码：

for (i = 1; i <= m; i++) {//开始从小到大枚举每一条边
    //判断一条边的两个顶点是否连通，即判断是否已在同一个集合中
    if (merge(e[i].u, e[i].v)) {//如果目前尚未不连通，则选用这条边
        counts++;
        sum += e[i].w;
    }
    if (counts == n - 1) //直到选用了n-1条边之后退出循环
        break;
}

Prim算法

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

最常见的问题就是：已知N座城市中任意两座城市之间建造道路所需要的费用，求最少花费多少就可以使得任意两座城市都可以通过所建造的道路互相到达。

算法核心：每在最小生成树集合中加入一个点就需要把这个点与集合外的点比较，不断的寻找两个集合之间最小的边。

算法的时间复杂度为O(N2)，空间复杂度为O(N2)。

基本步骤如下：

  1. 从任意个顶点开始构造生成树，假设就从1号顶点吧。首先将顶点1加入生成树中，用一个一维数组book来标记哪些顶点已经加入了生成树。
  2. 用数组dis记录生成树到各个顶点的距离。最初生成树中只有1号顶点，有直连边时，数组dis中存储的就是1号顶点到该顶点的边的权值，没有直连边的时候就是无穷大，即初始化dis数组。
  3. 从数组dis中选出离生成树最近的顶点(假设这个顶点为j)加入到生成树中(即在数组dis中找最小值)。再以j为中间点，更新生成树到每一个非树顶点的距离(就是松弛啦)，即如果dis[k]>e[j][k]则更新dis[k]=e[j][k]。
  4. 重复第3步，直到生成树中有n个顶点为止。

Prim算法核心代码：

//将1号顶点加入生成树
book[1] = 1; //这里用book来标记一个顶点是否已经加入生成树
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];
    //扫描当前顶点j的所有的边，再以j为中间点，更新生成树到每一个非树顶点的距离
    for (k = 1; k <= n; k++) {
        if (!book[k] && dis[k] > e[j][k])
            dis[k] = e[j][k];
    }
}