C++实现基于不相交集合的O(mlgn)复杂度的kruskal算法

目录

C++实现基于不相交集合的O(mlgn)复杂度的kruskal算法

不相交集合的数据构造kruskal 算法

知识补充

C++实现基于不相交集合的O(mlgn)复杂度的kruskal算法

本文实现完全参考<<Introduction to Algorithms Third edition>>,

不相交集合的数据构造

我们采用森林的方式实现不相交集合。这个森林是极简化的,每个节点只要一个指向父亲的指针,而且森林中的每一颗树都是一个集合,我们取树的根节点为这个集合的代表元。

1. int rank[505];
2. int father[505];
3. void make_set(int x)
4. {
5.         father[x]=x;
6.         rank[x]=0;
7. }
8. int find_set(int x)
9. {
10.     if (x!=father[x])
11.     {
12.         father[x]=find_set(father[x]);
13.     }
14.     return father[x];
15. }
16. void simply_union_set(int u,int v)
17. {
18.     u=find_set(u);
19.     v=find_set(v);
20.     father[u]=v;
21. }
22. void  perfect_union_set(int u,int v)
23. {
24.     u=find_set(u);
25.     v=find_set(v);
26.     if (rank[u]>rank[v])
27.     {
28.         father[v]=u;
29.     }
30.     else
31.     {
32.         father[u]=v;
33.         if(rank[u]==rank[v])
34.         rank[v]++;
35.     }
37. }

复制代码

可以看到在find_set()函数中采用了两趟遍历的思想,第一趟遍历找的根节点,第二趟遍历将途径上的节点全部指向根节点,完成了压缩树高。
在实现集合合并的时候,我们采用了两种方法:一种方法是直接合并simply_union_set,另一种是采用按秩合并的思想perfect_union_set,即总是让秩小合并到秩大的集合中,这是一种减少树高的有效战略;
当我们采用按秩合并时时,上述每一个操作的最差时间复杂度,都约等于O(1)
详情见<<Introduction to Algorithms Third edition>>中证明

kruskal 算法

1. void kruskal()
2. {
3.     for(int i=0;i<num_v;i++)make_set(i);
4.     sort(arr_edge.begin(),arr_edge.end(),mycompare);
5.     for(int i=0;i<arr_edge.size();i++)
6.     {
7.         int fr=arr_edge[i].fr;
8.         int to=arr_edge[i].to;
9.         int w=arr_edge[i].w;
10.         if( find_set(fr)!=find_set(to))
11.         {
12.                 result+=w;
13.             perfect_union_set(fr,to);
14.         }
15.     }
16. }

复制代码

kruskal 算法是一种基于贪婪战略的算法,它的时间复杂度的最大开销就是排序算法,即O(mlgm)=O(mlgn),这里m表示边数,n表示顶点数

知识补充

乘胜追击一下，通过一个例题再深化理解一下kruskal 算法吧
题目：http://poj.org/problem?id=2485
思路：就是最小生成树啊
代码

1. #include<iostream>
2. #include<algorithm>
3. #include<cstring>
4. #include<cstdio>
5. #include<vector>
6. using namespace std;
7. #define INTMAX 0x3f3f3f3f
8. typedef pair<int,int> pii;
9. typedef long long ll;
10. #define x first
11. #define y second
13. int rank[505];
14. int father[505];
15. int find_set(int x)
16. {
17.     if (x!=father[x])
18.     {
19.         father[x]=find_set(father[x]);
20.     }
21.     return father[x];
22. }
23. void simply_union_set(int u,int v)
24. {
25.     u=find_set(u);
26.     v=find_set(v);
27.     father[u]=v;
28. }
29. void  perfect_union_set(int u,int v)
30. {
31.     u=find_set(u);
32.     v=find_set(v);
33.     if (rank[u]>rank[v])
34.     {
35.         father[v]=u;
36.     }
37.     else
38.     {
39.         father[u]=v;
40.         if(rank[u]==rank[v])
41.         rank[v]++;
42.     }
44. }
45. struct edge
46. {
47.     int fr,to,w;
48. };
49. int num_case,num_v,result;
50. vector<edge> arr_edge;
52. void debug()
53. {
54.     for(int i=0;i<arr_edge.size();i++)
55.     {
56.         cout<<arr_edge[i].fr<<" to "<<arr_edge[i].to<<"="<<arr_edge[i].w<<endl;
57.     }
58. }
60. void init()
61. {
62.     arr_edge.clear();
63.     result=0;
64. }
65. void input()
66. {
67.     int w;
68.     scanf("%d",&num_v);
69.     for(int i=0;i<num_v;i++)
70.     {
71.         for(int j=0;j<num_v;j++)
72.         {
73.             scanf("%d",&w);
74.             if(i<j)
75.             {
76.                 edge temp;
77.                 temp.fr=i;
78.                 temp.to=j;
79.                 temp.w=w;
80.                 arr_edge.push_back(temp);
81.             }
82.         }
83.     }
85. }
86. bool mycompare(const edge& x,const edge &y)
87. {
88.     return x.w<y.w;
89. }
90. void kruskal()
91. {
92.     for(int i=0;i<num_v;i++)father[i]=i;
93.     sort(arr_edge.begin(),arr_edge.end(),mycompare);
94.     for(int i=0;i<arr_edge.size();i++)
95.     {
96.         int fr=arr_edge[i].fr;
97.         int to=arr_edge[i].to;
98.         int w=arr_edge[i].w;
99.         if( find_set(fr)!=find_set(to))
100.         {
101.             result=max(result,w);
102.             simply_union_set(fr,to);
103.         }
104.     }
105. }
106. void solve()
107. {
108.     init();
109.     input();
110.     //debug();
111.     kruskal();
112.     cout<<result<<endl;
113. }
115. int main()
116. {
117.     scanf("%d",&num_case);
118.     while(num_case--)
119.     {
120.         solve();
121.     }
122.     return 0;
123. }

复制代码

到此这篇关于C++实现基于不相交集合的O(mlgn)复杂度的kruskal算法的文章就介绍到这了,更多相关C++ kruskal算法内容请搜索网站以前的文章或继续阅读下面的相关文章希望大家以后多多支持网站！