最小生成樹演算法C++語言實作
1. Prim
思想：選擇離當前樹最近的點來擴充當前樹，直至邊數為n-1，因為要從候選點中選擇距離最近的點，直接實作比較困難，不如轉換一下，選擇當前最小生成樹中的點向外延伸的邊中最短的那條邊，使用優先佇列來維護向外延伸的邊，實作起來比較簡單，
#include <bits/stdc++.h>
using namespace std;
int n,m,a,b,v;
struct Edge{
int fr,to,l;
explicit Edge(int aa=0,int bb=0,int vv=0){fr=aa;to=bb;l=vv;}
bool operator<(const Edge& o) const{
return this->l>o.l;
}
};
vector<Edge> graph[100010];
bool flag[100010]; // flag[i]==true means node i is in tree;
Edge tree[100010];
void Prim(){
priority_queue<Edge> pq;
flag[1]=true;
int cnt=0;
for(Edge e:graph[1]){pq.push(e);}
while(cnt<n-1){
Edge top=pq.top();pq.pop();
if(flag[top.to]){continue;}
flag[top.to]=true;
tree[cnt++]=top;
for(Edge e:graph[top.to]){
if(!flag[e.to]){
pq.push(e);
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=0;i<m;++i) {
cin>>a>>b>>v;
Edge e1(a,b,v),e2(b,a,v);
graph[a].push_back(e1);
graph[b].push_back(e2);
}
Prim();
for(int i=0;i<n-1;++i){
Edge e=tree[i];
cout<<e.fr<<"->"<<e.to<<":"<<e.l<<endl;
}
}
/**
5 7
1 2 6
1 3 1
1 4 7
2 3 2
2 4 5
3 4 3
3 5 4
6 9
1 2 2
1 3 3
2 3 6
2 4 9
2 5 5
4 5 4
3 5 1
3 6 8
5 6 7
*/
2. Kruskal
思想：貪心每次選擇最小邊，將兩棵子樹歸并成一棵樹，如果最小邊的兩個端點屬于同一子樹，則跳過該邊，該場景符合并查集的使用場景，因此采用并查集實作，
#include <bits/stdc++.h>
using namespace std;
int n,m,a,b,v;
struct Edge{int fr,to,l;};
bool cmp(Edge e1, Edge e2){return e1.l<e2.l;}
Edge graph[100010];
Edge tree[100010];
int fa[100010];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int x,int y){fa[find(x)]=find(y);}
void Kruskal(){
for(int i=1;i<=n;++i){fa[i]=i;} // init UnionSet
sort(graph, graph+m,cmp);
for(int i=0,j=0;i<n-1&&j<m;++j){
Edge curr=graph[j];
if(find(curr.fr)!=find(curr.to)){
tree[i++]=curr;
merge(curr.fr,curr.to);
}
}
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=0;i<m;++i) {
cin>>graph[i].fr>>graph[i].to>>graph[i].l;
}
Kruskal();
for(int i=0;i<n-1;++i){
Edge e=tree[i];
cout<<e.fr<<"->"<<e.to<<":"<<e.l<<endl;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/259767.html
標籤：其他