TIP
最近老师在讲贪心算法的应用,最小生成树是其中最经典的应用之一,有时候知道其中的思想,但是用代码实现起来还是很有差距的,中午弄了几个小时prim
算法建最小生成树,但是最后还是没搞懂其中的关键,最后无法判断两个点是否是连通的,决定以后就用Kruskal
来解决这类问题吧。
# 迷之想法
中午用vector版本邻接表存储的无向图,我的想法是这样的,对每一个顶点域邻接的部分从小到大排序,这样求一个顶点到邻接点的最短距离直接取第一个点就好,等用完了这个点,就将它从该位置移除,与此同时,还要将它的主对角线对称位置也移除,就这样一步步运行下去,但是到最后,还是判断不了添加完的的多个点是否是连通状态,结果就卡在这了。
# 迷之代码
# 采用存储的方式
const int Max=1e4+2;
typedef struct EdgeNode
{
int to;
int w;
};
vector<EdgeNode> s[Max];//存储方式
vector<bool> f;
# 输入的方式
int n,m;
cin >> n >> m;//n代表点数,m代表边数
for(int k=0;k<m;k++){
int i,j,w;
cin >> i >> j >> w;
EdgeNode e;
e.to=j;
e.w=w;
s[i].push_back(e);
e.to=i;
s[j].push_back(e);
}
# 对邻接点按权值从小到大排序
bool cmp(EdgeNode x,EdgeNode y)
{
return x.w<y.w;
}
for(int i=1;i<=n;i++){
sort(s[i].begin(),s[i].end(),cmp);
}
# 处理并入点过程
int v=0;
vector<int> E;
E.push_back(1);
f[1]=true;
while(v!=5){
int key=0;
for(int i=0;i<E.size();i++){
if(s[E[key]][0].w>s[E[i]][0].w){
key=i;//找到已并入的点的最近点
}
}
f[s[E[key]][0].to]=true;//声明此点已被使用
E.push_back(s[E[key]][0].to);//将该点并入
cout <<"选:"<< E[key] << ' ' << s[E[key]][0].to << ' ' << s[E[key]][0].w << endl;
int j=0;
for(;j<s[s[E[key]][0].to].size();j++){
if(s[s[E[key]][0].to][j].to==E[key]){
break;
}
}//找到它关于主对角线的点
s[s[E[key]][0].to].erase(s[s[E[key]][0].to].begin()+j);
s[E[key]].erase(s[E[key]].begin());//删除
v++;
}
for(int i=1;i<=n;i++){
for(auto it=s[i].begin();it!=s[i].end();it++){
EdgeNode e=*it;
cout << i << ' ' << e.to << ' ' << e.w << endl;
}
}
记录下来,以后发现能解决了,再办它。
# 构建最小生成树
prim
算法建造最小生成树的时间复杂度是O(n^2)
,而Kruskal
的时间复杂度是eloge
,当边比较少时用Kruskal
效率会很好,以后边多的时候,也用它凑合着用吧,因为它主要消耗的时间就是排序,排完序后一切都好说,还有就是并查集了。
# 例题
假设有6个顶点,10条边,6个顶点分别用1,2,3,4,5,6表示,边的输入x y w
起点、终点、权值,问其中一颗最小生成树的组合,并求它的权值。
输入如下
6 10
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
5 3 6
5 6 6
6 3 4
6 4 2
4 3 5
# 代码如下
#include<bits/stdc++.h>
using namespace std;
const int Max=1e4+2;
int f[Max];
int e=0;//代表此刻边的数目
int sum=0;//权值之和
typedef struct EdgeNode
{
int from;
int to;
int w;
};
vector<EdgeNode> s;
void build(int n)
{
for(int i=1;i<=n;i++){
f[i]=i;
}
}
bool cmp(EdgeNode x,EdgeNode y)
{
return x.w<y.w;
}
int Find(int w)
{
return f[w]==w?w:f[w]=Find(f[w]);
}
bool che(int from,int to)
{
return Find(from)==Find(to);
}
void mer(int from,int to,int p)
{
if(!che(from,to)){
f[f[from]]=f[to];
sum+=s[p].w;
cout << "边有:" << from << ' ' << to << ' ' << s[p].w << endl;
e++;
}
}
int main()
{
int n,m;
cin >> n >> m;
build(n);
for(int k=0;k<m;k++){
int i,j,w;
cin >> i >> j >> w;
EdgeNode g;
g.from=i;
g.to=j;
g.w=w;
s.push_back(g);
}
sort(s.begin(),s.end(),cmp);
int p=0;
while(e!=n-1){
mer(s[p].from,s[p].to,p);//将边一个个送入去尝试
p++;
}
cout << "最小权值为:" << sum;
return 0;
}