普利姆算法(Prim)
-
思路
$dist[n] \rightarrow \infty$
$for(i = 0; i < n; i++)$
$t \leftarrow 找到集合外距离最近的点$
$用t更新其他点到集合的距离$
$st[t] = true$
集合:当前已在连通块中所有的点。
这里用st
数组来代表集合。
某一个点到集合的距离:这个点到集合内部的所有节点当中的长度最小的那个边,如果没有,距离定义为正无穷。
这里用dist
数组来代表某一个点到集合的距离。
我们将所有的边用邻接矩阵进行存储。
-
步骤
-
遍历 $N$ (节点数)次,取出当前集合与其他结点连接的边当中最小的那条边,并取出该边所连接的结点 $t$。
-
如果不是第一个点并且 $dist[t]$ 等于正无穷,说明当前距离最近的点到集合的距离为正无穷,说明这个图不连通,直接返回 $false$ 。
- 如果不是第一个点,$dist[t]$ 就表示的是当前这个点和当前已经连好的生成树里面某一条边的长度,故这里需要将答案路径长度直接加上这个边。
- $min(dist[j], g[t][j])$中的 $dist[j]$ 表示之前当点t没有加入集合时j到集合的距离,$g[t] [j]$ 表示如果点 $t$ 加入到集合后点j到集合的距离,从这两个数中取最小值,即点 $j$ 与该集合的最短距离。
-
将点 $t$ 加到集合里,即加入最小生成树里。
-
示例
如图,首先这里取出节点 $1$ ,然后将 $dist$ 数组更新为结点 $1$ 到其他节点的距离,即加入节点 $1$ 后的集合与剩下的节点的最短距离,并将节点加入到集合中。
第二次遍历时,我们继续遍历整个 $dist$ 数组,取出最短的边,由于与当前集合(节点 $1$ )的最短边为节点 $2$ 这条边,故第二次遍历我们取节点 $2$ 。因为集合到这个点的距离不为无穷,所以这里直接将答案加上集合到这个节点的边的值。接着我们将 $dist$ 更新为当前集合到每一个节点的边 和 节点 $2$ 到每一个节点的边 中最小的那个,即加入节点 $2$ 后的集合与剩下的节点的最短距离,最后将节点 $2$ 加入到集合中。接下来的遍历将重复进行上诉操作, 最后将 $res$ 值返回。
-
例题
给定一个 $n$ 个点 $m$ 条边的无向图,图中可能存在重边和自环,边权可能为负数。
求最小生成树的树边权重之和,如果最小生成树不存在则输出 impossible
。
给定一张边带权的无向图 $G=(V,E)$,其中 $V$ 表示图中点的集合,$E$ 表示图中边的集合,$n=|V|$,$m=|E|$。
由 $V$ 中的全部 $n$ 个顶点和 $E$ 中 $n−1$ 条边构成的无向连通子图被称为 $G$ 的一棵生成树,其中边的权值之和最小的生成树被称为无向图 $G$ 的最小生成树。
-
输入格式
第一行包含两个整数 $n$ 和 $m$。
接下来 $m$ 行,每行包含三个整数 $u,v,w$ 表示点 $u$ 和点 $v$ 之间存在一条权值为 $w$ 的边。
-
输出格式
共一行,若存在最小生成树,则输出一个整数,表示最小生成树的树边权重之和,如果最小生成树不存在则输出 impossible
。
-
数据范围
$1≤n≤500$,
$1≤m≤105$,
图中涉及边的边权的绝对值均不超过 $10000$。
-
输入样例:
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
-
输出样例:
6
-
代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int g[N][N], dist[N], n, m;
bool st[N];
int Prim()
{
int res = 0;
memset(dist, 0x3f, sizeof(dist));
for(int i = 0; i < n; i++)
{
int t = -1;
for(int j = 1; j <= n; j++)
{
if(!st[j] && (t == -1 || dist[j] < dist[t]))
t = j;
}
if(i && dist[t] == INF) return INF;
if(i)
{
res += dist[t];
}
for(int j = 1; j <= n; j++)
{
dist[j] = min(dist[j], g[t][j]);
}
st[t] = true;
}
return res;
}
int main()
{
cin >> n >> m;
memset(g, 0x3f, sizeof(g));
for(int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
g[a][b] = g[b][a] = min(g[a][b], c);
}
int t = Prim();
if(t == INF) puts("impossible");
else cout << t << endl;
return 0;
}