Kruskal算法求最小生成树
给定一个 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
题解：
Kruskal是基于全局贪心来完成，他的算法思想比较简单，只需要将边进行按小到大排序，并且保证入的边不会导致形成回路即可。
那么我们可以利用bool st[N]数组进行记录点，记录点是因为假设a,b,c点已经记录，那么接下来入c->d这条边的时候，若c，d在同一个集合当中，说明他们会形成回路。
#include<iostream>
using namespace std;
#include<queue>
#include<cstring>
const int N=200010,M=100010;
int n,m;
int p[M];
struct Edge{
int src;
int dst;
int weight;
Edge(int _src = -1, int _dst = -1, int _weight = -1)
:src(_src),
dst(_dst),
weight(_weight)
{}
bool operator<(const Edge& e)const
{
return this->weight > e.weight;
}
}Edges[N];
int Kruskal()//节点数量
{
priority_queue<Edge> pq;
auto GetRoot = [](int src){
while(p[src] >= 0)
{
src = p[src];
}
return src;
};
//每一条边入pq
for(int i = 0;i < N;++i)
{
pq.push(Edges[i]);
}
//cout << pq.top().weight << endl;
int res = 0;
int size = 0;
while(!pq.empty())
{
Edge e = pq.top();
pq.pop();
int srci = GetRoot(e.src);
int dsti = GetRoot(e.dst);
if(srci != dsti)
{
//一边加入另外一边
p[srci] += p[dsti];
p[dsti] = srci;
res += e.weight;
++ size;
}
else
{
continue;
}
}
if(size != n -1)
return -1;
else
return res;
}
int main()
{
cin >> n >> m;
//memset(h,-1,sizeof(h));//反码所以最后全是 1111 是吗
memset(p,-1,sizeof(p));//反码所以最后全是 1111 是吗
int j = 0;
while(m --)
{
int x,y,z;
cin >> x >> y >> z;
Edges[j++] = {x - 1,y - 1 , z};
}
int t = Kruskal();
if(t == -1)
{
cout << "impossible" << endl;
}
else
{
cout << t << endl;
}
return 0;
}
第二种写法，可以不借用优先级队列，直接使用sort进行边的排序即可。
#include<iostream>
using namespace std;
#include<cstring>
#include<cstdio>
const int N=200010,M=100010;
#include<algorithm>
int n,m;
int p[M];
struct Edge{
int src;
int dst;
int weight;
Edge(int _src = -1, int _dst = -1, int _weight = -1)
:src(_src),
dst(_dst),
weight(_weight)
{}
bool operator<(const Edge& e)const
{
return this->weight < e.weight;
}
}Edges[N];
int Kruskal()//节点数量
{
auto GetRoot = [](int src){
while(p[src] >= 0)
{
src = p[src];
}
return src;
};
//每一条边入pq
sort(Edges,Edges + m);
//cout << Edges[0].weight << endl;
int res = 0;
int size = 0;
for(int i = 0;i < m;++i)
{
int srci = GetRoot(Edges[i].src);
int dest = GetRoot(Edges[i].dst);
if(srci != dest)
{
p[srci] += p[dest];
p[dest] = srci;
res += Edges[i].weight;
++ size;
}
}
if(size != n -1)
return -1;
else
return res;
}
int main()
{
cin >> n >> m;
ios::sync_with_stdio(false);
//memset(h,-1,sizeof(h));//反码所以最后全是 1111 是吗
memset(p,-1,sizeof(p));//反码所以最后全是 1111 是吗
for(int i = 0;i < m;++i)
{
int x,y,z;
scanf("%d%d%d", &x, &y, &z);
Edges[i] = {x - 1,y - 1 , z};
}
int t = Kruskal();
if(t == -1)
{
cout << "impossible" << endl;
}
else
{
cout << t << endl;
}
return 0;
}
Prim算法求最小生成树
给定一个 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≤105,
1≤m≤2∗105,
图中涉及边的边权的绝对值均不超过 1000。
输入样例：
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
输出样例：
6
题解：
dist在这里是表示到达集合的距离。
- Prim基于局部贪心，由给定的一点出发，每次寻找离集合最近的一条边，dist记录的是
该点到集合的距离。这个点要十分注意，dist[j] = min(dist[j],g[t][j]);更新的代码也就有所不同，g[t][j]就是j这个点到集合的距离。 - 每次更新出一个点，更新这个点到其他点的距离，更新n轮，共n个点。
#include<iostream>
using namespace std;
#include<cstring>
const int N = 510;
int g[N][N];
int dist[N];
bool st[N];
int n,m;
int Prim()
{
dist[0] = 0;
int size = 0;
int res= 0;
for(; size < n; ++ size)
{
int t = -1;
//找最小的点进行更新
for(int j = 0;j < n; ++ j)
{
if(!st[j] && (t == -1 || dist[j] < dist[t]))//如果没有在树中，且到树的距离最短，则选择该点
t = j;
}
// for(int j = 0;j < n;++j)
// {
// cout << dist[j] << " ";
// }
//cout << "================" << endl;
//cout << t << " " << st[t] << " " << dist[t]<< endl;
if(dist[t] == 0x3f3f3f3f) return 0x3f3f3f3f;
st[t] = true;
res += dist[t];
//cout<< t + 1 << " " << res << endl;
for(int j = 0;j < n;++j)
{
if(g[t][j] != 0x3f3f3f3f && !st[j])//这个点不能是加入st数组当中的。
{
dist[j] = min(dist[j],g[t][j]);
//cout << t+1 << "->" << j+1 << ":" << dist[j] << " ";
}
}
//cout << endl;
}
if(size == n)
return res;
else
return 0x3f3f3f3f;
}
int main()
{
cin >> n >> m;
memset(dist,0x3f,sizeof(dist));
memset(g,0x3f,sizeof(g));
while(m --)
{
int x,y,z;
cin >> x>> y >> z;
if(x == y) continue;
g[x - 1][y - 1] = min(z,g[x-1][y - 1]);//重边
g[y - 1][x - 1] = g[x - 1][y - 1];//重边
}
int res = Prim();
if(res == 0x3f3f3f3f) cout << "impossible";
else cout << res << endl;
return 0;
}
end
- 喜欢就收藏
- 认同就点赞
- 支持就关注
- 疑问就评论