prim算法精讲

53. 寻宝（第七期模拟笔试）

题目描述：

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

不同岛屿之间，路途距离不同，国王希望你可以规划建公路的方案，如何可以以最短的总公路距离将所有岛屿联通起来。

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

输入描述：

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

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

输出描述：

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

输入示例：

输出示例：

解题思路

本题是最小生成树的模板题，最小生成树可以使用prim算法也可以使用kruskal算法计算出来。

最小生成树是所有节点的最小连通子图，即：以最小的成本（边的权值）将图中所有节点链接到一起。

图中有n个节点，那么一定可以用n-1条边将所有节点连接到一起。

那么如何选择这n-1条边就是最小生成树算法的任务所在。

prim算法，是从节点的角度采用贪心的策略每次寻找距离最小生成树最近的节点并加入到最小生成树中。

prim三部曲

第一步，选距离生成树最近节点
第二步，最近节点加入生成树
第三步，更新非生成树节点到生成树的距离（即更新minDist数组）

“每次寻找距离最小生成树最近的节点并加入到最小生成树中”，就用到了minDist数组，minDist数组用来记录每一个节点距离最小生成树的最近距离。

初始状态

minDist数组里的数值初始化为最大数，现在还没有最小生成树，默认每个节点距离最小生成树是最大的，这样后面我们在比较的时候，发现更近的距离，才能更新到minDist数组上。

第一步：选距离生成树最近节点

选择距离最小生成树最近的节点，加入到最小生成树，刚开始还没有最小生成树，所以随便选一个节点加入就好

第二步：最近节点加入生成树

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

第三步：更新非生成树节点到生成树的距离（即更新minDist数组）

#include<iostream>
#include<vector>
#include<climits>using namespace std;
int main(){int v,e;cin>>v>>e;int x,y,k;vector<vector<int>> grid(v+1,vector<int>(v+1,10001));while(e--){cin>>x>>y>>k;grid[x][y]=k;grid[y][x]=k;}// 所有节点到最小生成树的最小距离vector<int> minDist(v+1,10001);// 这个节点是否在树里vector<bool> isInTree(v+1,false);
// 我们只需要循环 n-1次，建立 n - 1条边，就可以把n个节点的图连在一起for(int i=1;i<v;i++){//1、第一步：选距离生成树最近节点int cur=-1;// 选中哪个节点 加入最小生成树int minVal=INT_MAX;for(int j=1;j<=v;j++){// 1 - v，顶点编号，这里下标从1开始//  选取最小生成树节点的条件：//  （1）不在最小生成树里//  （2）距离最小生成树最近的节点if(!isInTree[j]&&minDist[j]<minVal){minVal=minDist[j];cur=j;}}//2、第二步：最近节点（cur）加入生成树isInTree[cur]=true;//3、第三步：更新非生成树节点到生成树的距离（即更新minDist数组）// cur节点加入之后， 最小生成树加入了新的节点，那么所有节点到 最小生成树的距离（即minDist数组）需要更新一下// 由于cur节点是新加入到最小生成树，那么只需要关心与 cur 相连的 非生成树节点 的距离 是否比 原来 非生成树节点到生成树节点的距离更小了呢for(int j=1;j<=v;j++){// 更新的条件：// （1）节点是 非生成树里的节点// （2）与cur相连的某节点的权值 比 该某节点距离最小生成树的距离小// 很多录友看到自己 就想不明白什么意思，其实就是 cur 是新加入 最小生成树的节点，那么 所有非生成树的节点距离生成树节点的最近距离 由于 cur的新加入，需要更新一下数据了if(!isInTree[j]&&grid[cur][j]<minDist[j]){minDist[j]=grid[cur][j];}}}int res=0;for(int i=2;i<=v;i++){res+=minDist[i];}cout<<res<<endl;
}

拓展

上面讲解的是记录了最小生成树所有边的权值，如果让打印出来最小生成树的每条边呢？或者说要把这个最小生成树画出来呢？

此时有两个问题：

1、用什么结构来记录
2、如何记录

如果记录边，其实就是记录两个节点就可以，两个节点连成一条边。

如何记录两个节点呢？

我们使用一维数组就可以记录。parent[节点编号] = 节点编号，这样就把一条边记录下来了。（当然如果节点编号非常大，可以考虑使用map）

minDist数组里记录的其实也是最小生成树的边的权值。”

既然minDist数组记录了最小生成树的边，是不是就是在更新minDist数组的时候，去更新parent数组来记录一下对应的边呢。

所以在prim三部曲中的第三步，更新parent数组，代码如下：

for (int j = 1; j <= v; j++) {if (!isInTree[j] && grid[cur][j] < minDist[j]) {minDist[j] = grid[cur][j];parent[j] = cur; // 记录最小生成树的边 （注意数组指向的顺序很重要）}
}

如果 parent[cur] = j 这么写，最后更新的逻辑是 parent[1] = 2, parent[1] = 3， parent[1] = 4，最后只能记录节点1与节点4相连，其他相连情况都被覆盖了。

如果这么写 parent[j] = cur，那就是 parent[2] = 1, parent[3] = 1， parent[4] = 1 ，这样才能完整表示出节点1与其他节点都是链接的，才没有被覆盖。

kruskal算法精讲

53. 寻宝（第七期模拟笔试）

解题思路

prim 算法是维护节点的集合，而 Kruskal 是维护边的集合。

kruscal的思路：

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

而判断两个节点是否在同一个集合中，就用到了前面讲的并查集；

#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){if(father[u]==u)return u;father[u]=find(father[u]);return father[u];
}
void join(int u,int v){u=find(u);v=find(v);if(u==v)return;father[v]=u;
}int main(){int v,e;cin>>v>>e;int x,y,k;vector<Edge> edges; int res=0;vector<vector<int>> grid(v+1,vector<int>(v+1,10001));while(e--){cin>>x>>y>>k;edges.push_back({x,y,k});}sort(edges.begin(),edges.end(),[](const Edge& a,const Edge& b){return a.val<b.val;});init();for(Edge edge:edges){int i=find(edge.l);int j=find(edge.r);if(i!=j){res+=edge.val;join(i,j);}}cout<<res<<endl;return 0;
}