图论算法----最小生成树

图论经典算法

prim 算法（适合稠密图）

两个集合分别表示已加入的结点与未加入结点，每次贪心选择未加入结点中到已加入结点距离最短的结点加入第一个集合中，

更新一下距离，一直到所有结点都加入集合1中复杂度O(V*V) V为结点个数

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <set>
 5 #include <algorithm>
 6 #include <map>
 7 #include <queue>
 8 #include<vector>
 9 #define maxn 1010
10 #define maxm 100010
11 #define INF 0x3fffffff
12 using namespace std;
13 int mincost[maxn];
14 int G[maxn][maxn];
15 bool used[maxn];
16 int V;
17 int prim(){
18     for(int i=0;i<V;++i){
19         mincost[i]=INF;
20         used[i]=false;
21     }
22     mincost[0]=0;
23     int ans = 0;
24     while(true){
25         int v = -1;
26         for(int i=0;i<V;++i){
27             if(!used[i]&&(v==-1||mincost[i]<mincost[v]))v=i;
28         }
29         if(v==-1)break;
30         used[v]=true;
31         ans+=mincost[v];
32         for(int i=0;i<V;++i){
33             mincost[i]=min(mincost[i],G[v][i]);
34         }
35     }
36     return ans;
37 }
38 int main (){
39     while(scanf("%d",&V)!=EOF){
40         for(int i=0;i<V;++i){
41             for(int j=0;j<V;++j){
42                 scanf("%d",&G[i][j]);
43             }
44         }
45         printf("%d
",prim2());
46     }
47 }

View Code

可以优化一下，使用优先队列维护最小距离复杂度 O(V*log(E)) E 为边数

貌似写的比较渣

 1 typedef pair<int,int> P;//距离与结点id
 2 int prim2(){
 3     for(int i=0;i<V;++i){
 4         mincost[i]=INF;
 5         used[i]=false;
 6     }
 7     priority_queue<P,vector<P>,greater<P> >q;
 8     for(int i=1;i<V;++i){
 9         mincost[i]=G[0][i];
10         q.push(P(G[0][i],i));
11     }
12     int ans =0;
13     used[0]=true;
14     int cnt=1;
15     while(cnt<V){
16         P p = q.top();
17         q.pop();
18         if(used[p.second])continue;
19         used[p.second]=true;
20         ans+=p.first;
21         cnt++;
22         for(int i=0;i<V;++i){
23             if(!used[i]&&mincost[i]>G[p.second][i]){
24                 mincost[i]=G[p.second][i];
25                 q.push(P(G[p.second][i],i));
26             }
27         }
28     }
29     return ans;
30 }

View Code

kruskal 算法(稀疏图)

每次选择一条权值最小的边，如果两端点不是同一集合里则合并，答案加上权值，否则不做处理。复杂度O(Elog(E))

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <set>
 5 #include <algorithm>
 6 #include <map>
 7 #include <queue>
 8 #include<vector>
 9 #define maxn 1010
10 #define maxm 100010
11 #define INF 0x3fffffff
12 using namespace std;
13 struct edge{
14     int u,v,cost;
15     edge(){}
16     edge(int _u,int _v,int _cost){
17         u=_u;v=_v;cost=_cost;
18     }
19 };
20 bool cmp(edge a,edge b){
21     return a.cost<b.cost;
22 }
23 int V,E;
24 int father[maxn];
25 void init(){
26     for(int i=0;i<=V;++i){
27         father[i]=i;
28     }
29 }
30 int Find(int x){
31     return father[x]==x?x:father[x]=Find(father[x]);
32 }
33 void Union(int x,int y){
34     x = Find(x);
35     y = Find(y);
36     if(x!=y)father[x]=y;
37 }
38 bool same(int x,int y){
39     return Find(x)==Find(y);
40 }
41 edge G[maxm];
42 int cnt=0;
43 void addedge(int u,int v,int cost){
44     G[cnt++]=edge(u,v,cost);
45 }
46 int kruskal(){
47     sort(G,G+cnt,cmp);
48     init();
49     int ans=0;
50     for(int i=0;i<cnt;++i){
51         edge e = G[i];
52         if(!same(e.u,e.v)){
53             Union(e.u,e.v);
54             ans+=e.cost;
55         }
56     }
57     return ans;
58 }
59 int main (){
60     while(scanf("%d",&V)!=EOF){
61         cnt=0;
62         for(int i=0;i<V;++i){
63             for(int j=0;j<V;++j){
64                 int x;
65                 scanf("%d",&x);
66                 addedge(i,j,x);
67             }
68         }
69         printf("%d
",kruskal());
70     }
71 }

View Code

接下来就是撸题了