Prim/Kruskal求最小生成树

简单的纯板。prim算法适合稠密图，kruskal算法适合简单图。prim算法复杂度O(n^2)，n是图中点的个数，kruskal算法复杂度O(eloge)，e为图中边的条数。值得一提的是，加入堆优化的prim算法复杂度可达O(nloge)。

首先放一个很喜欢的kruskal。

 1 #include<bits/stdc++.h> 
 2 #define ll long long
 3 #define scan(i) scanf("%d",&i)
 4 using namespace std;
 5 const int MAXN=5005;//最大点数
 6 const int MAXM=250005;//最大边数
 7 int F[MAXN];//并查集使用
 8 int tol;//边数，加边前赋值为0
 9 struct Edge
10 {
11     int u,v,w;
12 }edge[MAXM];//储存边的信息，包括起点/终点/权值
13 void addedge(int u,int v,int w)
14 {
15     edge[tol].u=u;
16     edge[tol].v=v;
17     edge[tol++].w=w;
18 }
19 bool cmp(Edge a,Edge b)//排序函数，边按照权值从小到大排序
20 {
21     return a.w<b.w;
22 }
23 int Find(int x)
24 {
25     if(F[x]==-1)
26         return x;
27     else
28         return F[x]=Find(F[x]);
29 }
30 int Kruskal(int n)//传入点数，返回最小生成树的权值，如果不连通返回-1
31 {
32     memset(F,-1,sizeof(F));
33     sort(edge,edge+tol,cmp);
34     int cnt=0;//计算加入的边数
35     int ans=0;
36     for(int i=0;i<tol;i++){
37         int u=edge[i].u;
38         int v=edge[i].v;
39         int w=edge[i].w;
40         int t1=Find(u);
41         int t2=Find(v);
42         if(t1!=t2){
43             ans+=w;
44             F[t1]=t2;
45             cnt++;
46         }
47         if(cnt==n-1)
48             break;
49     }
50     if(cnt<n-1) return -1;//不连通
51     else return ans;
52 }
53 int n,m;
54 int w,u,v;
55 int main(){
56     while(scanf("%d%d",&n,&m)!=EOF){
57         tol=0;
58         for(int i=1;i<=m;i++){
59             scanf("%d%d%d",&u,&v,&w);
60             addedge(u,v,w);
61         }
62         cout<<Kruskal(n)<<endl;
63     }
64     return 0;
65 }

这个是用链式前向星存边+堆优化的prim算法。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=5005;
 4 struct Edge{
 5     int to,dist;
 6     Edge(int t,int d):to(t),dist(d){}
 7     bool operator<(const Edge& e)const{
 8         return dist>e.dist;
 9     }
10 };
11 int n,m;
12 bool vis[maxn];
13 vector<Edge> g[maxn];
14 priority_queue<Edge> que;
15 void prim(){
16     memset(vis,0,sizeof(vis));
17     while(que.size()) que.pop();
18 
19     for(int i=0;i<g[0].size();++i) que.push(g[0][i]);
20     vis[0]=true;
21 
22     int ans=0;
23     for(int cnt=1;cnt<n;++cnt){
24         while(que.size() && vis[que.top().to]) que.pop();
25         Edge e=que.top();
26         ans+=e.dist;
27         int v=e.to;
28         vis[v]=true;
29         for(int i=0;i<g[v].size();++i){
30             if(!vis[g[v][i].to]) que.push(g[v][i]);
31         }
32     }
33     for(int i=0;i<n;i++){
34         if(vis[i]==false){
35             printf("orz
");
36             return;
37         }
38     } 
39     printf("%d
",ans);
40 }
41 
42 int main(){
43     while(scanf("%d%d",&n,&m)==2){
44         for(int i=0;i<n;++i) g[i].clear();
45         for(int i=0;i<m;++i){
46             int u,v,w;
47             scanf("%d%d%d",&u,&v,&w);
48             g[u-1].push_back(Edge(v-1,w));
49             g[v-1].push_back(Edge(u-1,w));
50         }
51         prim();
52     }
53     return 0;
54 }