代码随想录算法训练营Day49 | Prim算法、Kruskal算法-编程阁

Prim算法

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

1.思路

本题是最小生成树的模板题，图中有n个节点，那么一定可以用 n-1 条边将所有节点连接到一起，并且总权重最小。

Prim 算法：从一个顶点开始，逐步“生长”出一棵树。每次都选择一条权重最小的边，这条边连接一个新顶点到当前已经构建好的树上。这个过程不断重复，直到所有顶点都被包含进来。

Prim 算法核心：

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

这道题的解题思路为：

初始化
- 任意选择一个顶点作为树的起点（默认是顶点1）。
- 创建一个集合（isIntree数组），用来记录哪些顶点已经加入了树。
- 创建一个距离表（minDist数组），用来记录尚未加入树的顶点，到当前树的最短距离是多少。初始时，所有距离都是“无穷大”。
循环n-1次（因为最终树有n-1条边）
- 选距离生成树最近节点
  - 在所有还没加入树的顶点中，找到一个距离当前树最近的顶点。即在minDist表中记录的值最小的顶点。
- 最近节点加入生成树
  - 将这个找到的顶点标记为“已加入树”。
  - 此时，连接它和树的那条边，就正式成为了最小生成树的一条边。
- 更新非生成树节点到生成树的距离（即更新minDist数组）
  - 由于树中多了一个新顶点，其他未加入树的顶点到树的距离可能会变得更短
  - 遍历这个新顶点的所有邻居，如果通过新顶点到某个邻居的距离，比该邻居之前记录的距离更短，就更新这个邻居的距离。
结束
- 重复n-1次后，所有顶点都已加入树，最小生成树就构建完成了。
- 我们把每次加入树时所用的那条边的权重（即minDist中最终记录的值）加起来，就是最终结果。

#include <iostream> #include <vector> using namespace std; int main(){ int n,m;cin>>n>>m; vector<vector<int>>graph(n+1,vector<int>(n+1,10001)); for(int i=0;i<m;i++){ int s,t,val;cin>>s>>t>>val; // 因为是双向图，所以两个方向都要填上 graph[s][t]=val; graph[t][s]=val; } // 这个节点是否在树里 vector<bool>isIntree(n+1,false); // 所有节点到最小生成树的最小距离 vector<int>minDist(n+1,10001); for(int i=1;i<n;i++){ // 1、prim三部曲，第一步：选距离生成树最近节点 int minval=10001; int cur=1; for(int j=1;j<=n;j++){ // 选取最小生成树节点的条件： // （1）不在最小生成树里 // （2）距离最小生成树最近的节点 if(!isIntree[j] && minDist[j]<minval){ minval=minDist[j]; cur=j; } } // 2、prim三部曲，第二步：最近节点（cur）加入生成树 isIntree[cur]=true; // 3、prim三部曲，第三步：更新非生成树节点到生成树的距离（即更新minDist数组） for(int j=1;j<=n;j++){ // 更新的条件： // （1）节点是 非生成树里的节点 // （2）与cur相连的某节点的权值 比 该某节点距离最小生成树的距离小 if(!isIntree[j] && graph[cur][j]<minDist[j]){ minDist[j]=graph[cur][j]; } } } int res=0; // 不计第一个顶点，因为统计的是边的权值，v个节点有 v-1条边 for(int i=2;i<=n;i++){ res+=minDist[i]; } cout<<res<<endl; return 0; }

2.拓展

在上述问题的基础上还要打印出最小生成树的每条边。

要存边，我们可以使用一维数组来记录，parent [节点编号] = 节点编号，这样就把一条边记录下来了。minDist 数组记录了最小生成树的边，所以在更新 minDist 数组的时候，就更新 parent 数组来记录对应的边。

#include <iostream> #include <vector> using namespace std; int main(){ int n,m;cin>>n>>m; vector<vector<int>>graph(n+1,vector<int>(n+1,10001)); for(int i=0;i<m;i++){ int s,t,val;cin>>s>>t>>val; graph[s][t]=val; graph[t][s]=val; } vector<bool>isIntree(n+1,false); vector<int>minDist(n+1,10001); vector<int>father(n+1,-1); for(int i=1;i<n;i++){ int minval=10001; int cur=1; for(int j=1;j<=n;j++){ if(!isIntree[j] && minDist[j]<minval){ minval=minDist[j]; cur=j; } } isIntree[cur]=true; for(int j=1;j<=n;j++){ if(!isIntree[j] && graph[cur][j]<minDist[j]){ minDist[j]=graph[cur][j]; father[j]=cur; // 记录边 } } } int res=0; for(int i=2;i<=n;i++){ res+=minDist[i]; } cout<<res<<endl; // 输出 最小生成树边的链接情况 for(int i=1;i<=n;i++){ cout<<i<<"->"<<father[i]<<endl; } return 0; }

3.思考

Prim 算法三部曲：

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

minDist 数组是 prim 算法的灵魂，它帮助 prim 算法完成最重要的一步，就是如何找到距离最小生成树最近的点。

4.Reference：prim算法精讲 | 代码随想录

Kruskal算法

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

1.思路

与 Prim 算法从一个顶点“生长”不同，Kruskal 算法的核心思想是直接对所有的边进行操作。它按照边的权重从小到大的顺序，依次将边加入图中，只要这条边不会与已经选择的边形成环路，就将其纳入最小生成树。为了高效地判断环路，引入之前的并查集。

Kruscal 的思路：

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

#include <iostream> #include <vector> #include <algorithm> using namespace std; int n,m; struct Edge{ int s,t,val; }; bool cmp(const Edge& a,const Edge& b){ return a.val<b.val; } vector<int>father(n+1,1); void init(){ for(int i=1;i<=n;i++){ father[i]=i; } } int find(int u){ if(u==father[u]){ return u; } return father[u]=find(father[u]); } bool issame(int u,int v){ u=find(u); v=find(v); return u==v; } void join(int u,int v){ u=find(u); v=find(v); if(u==v) return; father[u]=v; } int main(){ cin>>n>>m; vector<Edge> edges; for(int i=0;i<m;i++){ int s,t,val;cin>>s>>t>>val; edges.push_back({s,t,val}); } // 按边的权值对边进行从小到大排序 sort(edges.begin(),edges.end(),cmp); init(); int res=0; // 从头开始遍历边 for(int i=0;i<m;i++){ // 检查这条边的两个顶点是否已经连通 if(!issame(edges[i].s,edges[i].t)){ join(edges[i].s,edges[i].t); res+=edges[i].val; // 这条边可以作为生成树的边，将这条边的权重累加到结果中 } } cout<<res<<endl; return 0; }

2.拓展

在上述问题基础上将最小生成树的边输出。

因为 Kruskal 本来就是直接操作边，边的结构自然清晰。当判断两个节点不在同一个集合的时候，这两个节点的边就加入到最小生成树，此时把生成树的边保存下来就可以了。

#include <iostream> #include <vector> #include <algorithm> using namespace std; int n,m; struct Edge{ int s,t,val; }; bool cmp(const Edge& a,const Edge& b){ return a.val<b.val; } vector<int>father(n+1,1); void init(){ for(int i=1;i<=n;i++){ father[i]=i; } } int find(int u){ if(u==father[u]){ return u; } return father[u]=find(father[u]); } bool issame(int u,int v){ u=find(u); v=find(v); return u==v; } void join(int u,int v){ u=find(u); v=find(v); if(u==v) return; father[u]=v; } int main(){ cin>>n>>m; vector<Edge> edges; for(int i=0;i<m;i++){ int s,t,val;cin>>s>>t>>val; edges.push_back({s,t,val}); } sort(edges.begin(),edges.end(),cmp); init(); int res=0; // 存储最小生成树的边 vector<Edge> result; for(int i=0;i<m;i++){ if(!issame(edges[i].s,edges[i].t)){ join(edges[i].s,edges[i].t); // 保存最小生成树的边 result.push_back(edges[i]); res+=edges[i].val; } } cout<<res<<endl; for(Edge edge:result){ cout<<edge.s<<"->"<<edge.t<<" : "<<edge.val<<endl; } return 0; }