算法日记 47 day 最小生成树（prim,kruskal）

今天主要是针对最小生成树的两种算法。

用题目来举例

题目：寻宝

53. 寻宝（第七期模拟笔试） (kamacoder.com)

题目描述

在世界的某个区域，有一些分散的神秘岛屿，每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路，方便运输。

不同岛屿之间，路途距离不同，国王希望你可以规划建公路的方案，如何可以以最短的总公路距离将所有岛屿联通起来（注意：这是一个无向图）。

给定一张地图，其中包括了所有的岛屿，以及它们之间的距离。以最小化公路建设长度，确保可以链接到所有岛屿。

输入描述

第一行包含两个整数V 和 E，V代表顶点数，E代表边数。顶点编号是从1到V。例如：V=2，一个有两个顶点，分别是1和2。

接下来共有 E 行，每行三个整数 v1，v2 和 val，v1 和 v2 为边的起点和终点，val代表边的权值。

输出描述

输出联通所有岛屿的最小路径总距离

输入示例

输出示例

提示信息

数据范围：
2 <= V <= 10000;
1 <= E <= 100000;
0 <= val <= 10000;

如下图，可见将所有的顶点都访问一遍，总距离最低是6.

题目分析：

实际上就是寻找最小连通子图，以最小的成本（边的权值）将图中所有节点链接到一起。

那么，对于n个结点，就需要n-1条边来将他们连起来。所以我们就需要在所有的边里面选出n-1条边。来看看两种算法怎么选出这些边。

prim算法

prim算法呢，主要维护的结点的信息，他的思路类似于贪心的策略，每次选代价最小的结点加入到最小生成树中，所以prim算法的三个步骤就是

1.寻找离最小生成树最近的结点

2.将最近结点加入最小生成树

3.更新结点离最小生成树最近的距离

所以我们用一个数组minDist来记录每一个结点距离最小生成树的距离，初始为结点数加1即可。为了方便和结点对应，这个数组我们也开始从1开始使用。

所以他的初始状态为

那么开始构造最小生成树，这边直接选取第一个结点加入最小生成树就好了

1、prim三部曲，第一步：选距离生成树最近节点

选择距离最小生成树最近的节点，加入到最小生成树，刚开始还没有最小生成树，所以随便选一个节点加入就好（因为每一个节点一定会在最小生成树里，所以随便选一个就好），那我们选择节点1 （符合遍历数组的习惯，第一个遍历的也是节点1）

2、prim三部曲，第二步：最近节点加入生成树

此时节点1 已经算最小生成树的节点。

3、prim三部曲，第三步：更新非生成树节点到生成树的距离（即更新minDist数组）

接下来，我们要更新所有节点距离最小生成树的距离，如图：

注意下标0，我们就不管它了，下标 1 与节点 1 对应，这样可以避免大家把节点搞混。

此时所有非生成树的节点距离最小生成树（节点1）的距离都已经跟新了。

节点2 与节点1 的距离为1，比原先的距离值10001小，所以更新minDist[2]。
节点3 和节点1 的距离为1，比原先的距离值10001小，所以更新minDist[3]。
节点5 和节点1 的距离为2，比原先的距离值10001小，所以更新minDist[5]。

注意图中我标记了 minDist数组里更新的权值，是哪两个节点之间的权值，例如 minDist[2] =1 ，这个 1 是节点1 与节点2 之间的连线，清楚这一点对最后我们记录最小生成树的权值总和很重要。

1、prim三部曲，第一步：选距离生成树最近节点

选取一个距离最小生成树（节点1）最近的非生成树里的节点，节点2，3，5 距离最小生成树（节点1）最近，选节点 2（其实选节点3或者节点2都可以，距离一样的）加入最小生成树。

2、prim三部曲，第二步：最近节点加入生成树

此时节点1 和节点2，已经算最小生成树的节点。

3、prim三部曲，第三步：更新非生成树节点到生成树的距离（即更新minDist数组）

接下来，我们要更新节点距离最小生成树的距离，如图：

此时所有非生成树的节点距离最小生成树（节点1、节点2）的距离都已经跟新了。

节点3 和节点2 的距离为2，和原先的距离值1 小，所以不用更新。
节点4 和节点2 的距离为2，比原先的距离值10001小，所以更新minDist[4]。
节点5 和节点2 的距离为10001（不连接），所以不用更新。
节点6 和节点2 的距离为1，比原先的距离值10001小，所以更新minDist[6]。

剩下的步骤就是重复这个过程，我这里就不写了

看看具体的代码实现

#include<iostream>
#include<vector>
#include <climits>
 
using namespace std;
 
int main(){
    int v,e;
    int x,y,value;
     
    cin>>v>>e;
    vector<vector<int>>grid(v+1,vector<int>(v+1,10001));
    while(e--){
        cin>>x>>y>>value;
        //无向图
        grid[x][y]=value;
        grid[y][x]=value;
    }
     
    //记录每一个节点到最小生成树节点的最小距离
    vector<int> minDist(v+1,10001);
     
    //记录节点是否在最小生成树中
    vector<bool> isInTree(v+1,false); 
     
    //n个节点，需要n-1条边来连通
    //遍历构建n-1条边(所有数组从1开始，方便对应)
    for(int i=1;i<v;i++){//n-1条边
     
        //1.prim三部曲，选取里最小生成树最近的节点，加入最小生成树
         
        int cur_idx=-1;//选取的节点
        int min_Value=INT_MAX;
         
        //遍历minDist,寻找最近节点
        for(int j=1;j<=v;j++){
            if(!isInTree[j]&&minDist[j]<min_Value){
                cur_idx=j;
                min_Value=minDist[j];
            }
        }
         
        //2.将最小节点加入到最小生成树中
        isInTree[cur_idx]=true;
         
        //3.更新minDist,更新为离最小生成树最近的距离
        for(int j=1;j<=v;j++){
            //更新的条件： 1.不在最小生成树中 2.这个节点和cur节点的距离，比之前里最小生成树的距离小
            if(!isInTree[j]&&grid[cur_idx][j]<minDist[j]){
                minDist[j]=grid[cur_idx][j];
            }
        }
    }
     
    //构建完成最小生成树
     
    //统计结果
    int result = 0;
    for (int i = 2; i <= v; i++) { // 不计第一个顶点，因为统计的是边的权值，v个节点有 v-1条边
        result += minDist[i];
    }
    cout << result << endl;
}

krusal算法

不同于prim算法的处理结点，kruskal选择处理的是边，

来看看它的具体思路

krusal的思路：

边的权值排序，因为要优先选最小的边加入到生成树里
遍历排序后的边
- 如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环
- 如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合

可以看到，krusal 算法主要在于判断两个点是否在同一个集合中（最小生成树）,这一部分，就需要用到并查集了，

看看图解

将图中的边按照权值有小到大排序，这样从贪心的角度来说，优先选权值小的边加入到最小生成树中。

排序后的边顺序为[(1,2) (4,5) (1,3) (2,6) (3,4) (6,7) (5,7) (1,5) (3,2) (2,4) (5,6)]

(1,2) 表示节点1 与节点2 之间的边。权值相同的边，先后顺序无所谓。

开始从头遍历排序后的边。

选边(1,2)，节点1 和节点2 不在同一个集合，所以生成树可以添加边(1,2)，并将节点1，节点2 放在同一个集合。

选边(4,5)，节点4 和节点 5 不在同一个集合，生成树可以添加边(4,5) ，并将节点4，节点5 放到同一个集合。

继续这个思路，就可以把所有的点都加到最小生成树中了，看看具体的代码实现

#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;
 
struct Edge{
    int l,r,val;
};
 
int n=10001;//节点数
vector<int> father(n,-1);
 
void init(){
    for(int i=0;i<n;i++){
        father[i]=i;
    }
}
 int find(int u){
     return u==father[u]?u:father[u]=find(father[u]);
 }
  
 void join(int u,int v){
     u=find(u);
     v=find(v);
     if(u==v) return;
     father[v]=u;
 }
  
 bool isSame(int u,int v){
     u=find(u);
     v=find(v);
     return u==v;
 }
  
 int main(){
     int v,e;
     int v1,v2,val;
     int result_val=0;
     cin>>v>>e;
     vector<Edge> edges; //记录边
     while(e--){
         cin>>v1>>v2>>val;
         edges.push_back({v1,v2,val});
     }
      
    // 执行Kruskal算法
    // 按边的权值对边进行从小到大排序
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
            return a.val < b.val;
    });
     
    init();//初始化并查集
     
    // 从头开始遍历边
    for (Edge edge : edges) {
        // 并查集，搜出两个节点的祖先
        int x = find(edge.l);
        int y = find(edge.r);
 
        // 如果祖先不同，则不在同一个集合
        if (x != y) {
            result_val += edge.val; // 这条边可以作为生成树的边
            join(x, y); // 两个节点加入到同一个集合
        }
    }
    cout << result_val << endl;
    return 0;
 }

所以，总的来看，最小生成树的两种算法各有各的侧重，那么对于一些边少节点多的情况我们使用Krusal算法，反之Prim算法即可。

对于更详细的解析与其他语言的代码块，可以去代码随想录上查看。

代码随想录 (programmercarl.com)