图论-最小生成树

Prim算法

算法描述

dist[i]<-- $\infty$

for(i =0;i<n;i++)

t<--找到集合外最近的点

用t更新其他点到集合的距离（这个集合就是已经确定的最小生成树的点和边）

st[t] = true;

dist[i] <-- 无穷

这一步是初始化所有节点到集合的最小距离为无穷大。dist[i] 表示从已选节点集合到节点 i 的最小边权值。在算法开始时，所有的节点距离都是无穷大，因为还没有选择任何节点。
```
for (i = 0; i < n; i++) {dist[i] = INF; // INF 代表无穷大
}
```
for (i = 0; i < n; i++)

这是一个循环，用来初始化每个节点的距离。通常情况下，这里的 n 是图中节点的数量。在 Prim 算法中，我们会从集合中逐步选出节点，因此一开始要设置所有节点的距离。
```
for (i = 0; i < n; i++) {// 初始化 dist 数组
}
```
t <-- 找到集合外最近的点

这一部分是 Prim 算法的核心。t 是当前最小生成树（MST）中包含的节点集合之外的节点中，距离集合最近的节点。这个节点 t 是当前最小边权值的节点，且这个节点在生成树中尚未包含。
```
int t = -1;
for (i = 0; i < n; i++) {if (!st[i] && (t == -1 || dist[i] < dist[t])) {t = i;}
}
```
在这个代码片段中，st 是一个布尔数组，用来表示节点是否已被加入到生成树中。dist[i] 是节点 i 到生成树中节点的最小距离。
用 t 更新其他点到集合的距离

一旦找到 t，你需要更新所有与 t 相连的、尚未被包含在生成树中的节点的距离。如果通过 t 到某个节点 v 的边权值更小，就更新 dist[v]。
```
for (每个与 t 相连的节点 v) {if (!st[v] && edge(t, v) < dist[v]) {dist[v] = edge(t, v);}
}
```
这里 edge(t, v) 表示从节点 t 到节点 v 的边的权值。
st[t] = true

最后，将 t 标记为已经包含在生成树中。这表示节点 t 现在是最小生成树的一部分，不再需要考虑 t 的边来更新其他节点的距离。
```
st[t] = true;
```
这里 st 是一个布尔数组，st[i] 为 true 表示节点 i 已经被包含在生成树中。

图例

已知有下面树：

第一步：初始化，将所有点距离集合的距离设置为无穷，此时所有点都没有加入集合。

将节点1加入集合(此时所有点距离集合都是inf，所以可以随便找到一个点

根据节点1更新其他点到集合的最小距离，暂时将2、3、4更新为(1)(2)(3)。

然后将节点1放入集合

再找到集合外最近的点2号点。

根据2号点更新其他不在集合的点的距离，此时没有借助2号点能变得更小的，因此不变。

将2号点放入集合中。

再次找到不在集合中的最小的点，即3号点。

根据3号点更新距离，没有改变

将3号点放入集合

继续找4号点，也没有更新距离。

算法结束。

例题

858. Prim算法求最小生成树 - AcWing题库

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N =510,INF=100000000;
int g[N][N],dist[N];
bool st[N];
int n,m;int prim(){fill(dist,dist+N,INF);int res=0;dist[1] = 0;//把第一个点设置为0方便后面操作。for(int i=0;i<n;i++){int t=-1;for(int j=1;j<=n;j++){if(!st[j] && (t ==-1 || dist[t] > dist[j])){//注意，这里是比较dist[t] > dist[j],在st==false的点中找到一个最小的t = j;}}if(dist[t]==INF){return INF;}//不是第一次轮回的，一定有一个最小的点，如果没有说明不连通。res += dist[t];//这两步一定要在前面，因为这是将t放入集合，后面才不会再次更新t了st[t] = true;//根据节点t更新其他距离。for(int j=1;j<=n;j++){if(!st[j]){dist[j] = min(dist[j],g[t][j]);//这里省去了判断两个点是否有边，即使没有边也是INF}}}return res;}int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){g[i][j] = INF;}}for(int i=0;i<m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);g[a][b] = g[b][a] = min(c,g[a][b]);//一定要注意只存储最小边。}for(int i=1;i<=n;i++) g[i][i] = 0;//解决自环问题int ans = prim();if(ans == INF) printf("impossible");else printf("%d",ans);return 0;
}

Kruskal算法

算法描述：

将每一条边按照权重从小到大排序

枚举每一条边a,b权重是c

如何a、b所在集合不连通，将a-b加入到集合中去。

这里判断a、b是否在同意集合需要用并查集来解决。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5+10,M=2*N;
int res,p[N],n,m,st[N],cnt;
struct E{int a,b,w;bool operator<(const E &e){return this->w<e.w;}
}Edges[M];//注意存储的是边int myfind(int x){if(x!=p[x]) p[x] = myfind(p[x]);return p[x];
}int krus(){for(int i=1;i<=m;i++){E e = Edges[i];int sa = myfind(e.a);int sb = myfind(e.b);if(sa != sb){res+=e.w;p[sb] = sa;cnt++;}}if(cnt<n-1) return 0;return res;
}int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){p[i] = i;}for(int i=1;i<=m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);Edges[i].a=a;Edges[i].b=b;Edges[i].w=c;}sort(Edges+1,Edges+m+1);int tag = krus();if(tag==0) cout<<"impossible";else{cout<<tag;}return 0;
}