最小生成树算法(Prim+Kruskal)

Prim算法：

首先任取一个点u加入最小生成树

1)更新从其他点v出发到u的距离储存在dist中

2)然后选一个dist值最小的点u(1)再收入到最小生成树中，再重复1)

当点全部收录最小生成树时，算法结束

代码如下：

#include<iostream> #include<cstdio> #include<queue> #include<algorithm> using namespace std; const int INF=1<<30; struct Edge{ int vex; int w; Edge(int v=0,int w=INF):vex(v),w(w){} bool operator < (const Edge& e) const { return w>e.w; } }; //图是邻接表存储 G[u]储存u点出发所有的点 vector<vector<Edge> > G(110); //比Vector<Edge> G[110] 快 int HeapPrim(int n) //返回mst的最小权值 { priority_queue<Edge> PQ; vector<int> dist(n,INF); //所有点到mst的最短距离 vector<bool> used(n,false); int totw=0; //mst 的总权值 int DoneNum=0; //收入的点数 PQ.push(Edge(0,0)); while(DoneNum<n&&!PQ.empty()) { Edge e=PQ.top(); PQ.pop(); while(used[e.vex]&&!PQ.empty()) e=PQ.top(),PQ.pop(); if(used[e.vex]) continue; //不能 if(PQ.empty())因为第一个点就是empty的 totw+=e.w; used[e.vex]=true; DoneNum++; for(int i=0;i<G[e.vex].size();i++) //该点连接的所有边 { int v=G[e.vex][i].vex; int w=G[e.vex][i].w; if(!used[v]&&dist[v]>w){ //更新到mst的dist值 dist[v]=w; PQ.push(Edge(v,w)); } } } if(DoneNum<n) return -1; return totw; } int main() { int n; while(cin>>n) { for(int i=0;i<n;i++) G[i].clear(); for(int i=0;i<n;i++) //邻接矩阵读取 for(int j=0;j<n;j++) { int w; cin>>w; if(i!=j) G[i].push_back(Edge(j,w)); } cout<<HeapPrim(n)<<endl; } return 0; }

kruskal算法：

更简单，每条边权值排排序，再从小到大选n-1个边就好了  (n为顶点数)

但要注意每条边的两个顶点不能都在同一个集合，所以要用到并查集优化了

#include<iostream> #include<cstdio> #include<vector> #include<algorithm> using namespace std; const int maxn=10000+5; int n,m; //n个点 , m条边 struct Edge{ int from,to,weight; Edge(int f,int t,int w):from(f),to(t),weight(w){} bool operator < (const Edge& e) const { return weight<e.weight; } }; vector<Edge> edges; int p[maxn]; int find(int x) { return p[x]==x?x:p[x]=find(p[x]); } int Kruskal() { int TotW=0; for(int i=0;i<n;i++) p[i]=i; sort(edges.begin(),edges.end()); int done=0; for(int i=0;i<m;i++) { Edge e=edges[i]; int u=e.from, v=e.to, w=e.weight; int up=find(u), vp=find(v); if(up!=vp) TotW+=w,p[up]=vp,done++; if(done==n-1) break; //到n-1条边就结束 } return TotW; } int main() { while(cin>>n) { edges.clear(); for(int i=0;i<n;i++) //邻接矩阵读取 for(int j=0;j<n;j++) { int w; cin>>w; if(i!=j) edges.push_back(Edge(i,j,w)); } m=edges.size(); cout<<Kruskal()<<endl; } return 0; }