本文共 8135 字，大约阅读时间需要 27 分钟。
- 图相关算法的实现。
可视化的来看连接问题：
左上右下是否是连接的呢？
意义：实际应用中的作用
网络中节点间的连接状态
社交网络：Facebook中用户a和b中的联系（好友关系）。是否能联系到。
音乐电影书籍，多媒体之间形成网络。
互联网网页之间形成的网络
路由器和路由器之间形成的也是网络
道理交通，航班调度都是网络
数学中的集合类实现
并就是实现并集。& 查询
连接问题 & 路径问题
比路径问题要回答的问题少（路径是什么，连接问题只问有没有连）
- 和二分查找作比较：顺序查找法顺便回答了rank。和前面其他元素的位置- 和select作比较：排好序回答问题更多。快排思路select回答问题更少- 和堆作比较：只关心最大最小。
除了回答问题本身之外是不是额外的回答了别的问题。很有可能就存在
更高效的算法。：因为高效算法不需要回答额外的问题。对于一组数据，主要支持两个动作：
- union( p , q )- find( p )
用来回答一个问题
- isConnected( p , q )
最简单的表示方式；
数组。0,1.0-4是一组，5-9是一组。组内之间有联系
奇数是一组，偶数是一组。
namespace UF1 { class UnionFind { private: int *id; int count; public: UnionFind(int n) { count = n; id = new int[n]; for (int i = 0; i < n; i++) id[i] = i; } ~UnionFind() { delete[] id; }//传入元素p，返回元素对应的id。 int find(int p) { assert(p >= 0 && p < count); return id[p]; } bool isConnected(int p, int q) { return find(p) == find(q); } //传入两个元素，并 void unionElements(int p, int q) { //找到两个元素的id int pID = find(p); int qID = find(q); //比较id if (pID == qID) return; for (int i = 0; i < count; i++) //从头到尾的扫描时间复杂度O(n) if (id[i] == pID) id[i] = qID; } };} Testhelper.h:
namespace UnionFindTestHelper{ //n是数据量 void testUF1( int n ){ srand( time(NULL) ); UF1::UnionFind uf = UF1::UnionFind(n); time_t startTime = clock(); for( int i = 0 ; i < n ; i ++ ){ int a = rand()%n; int b = rand()%n; uf.unionElements(a,b); //O(n） } for(int i = 0 ; i < n ; i ++ ){ int a = rand()%n; int b = rand()%n; uf.isConnected(a,b); //时间复杂度只有O(1) } time_t endTime = clock(); cout<<"UF1, "<<2*n<<" ops, "< main.cpp:
int main() { int n = 100000; UnionFindTestHelper::testUF1(n); return 0;} 运行结果：
quick find 查找时只需要O(1)级别。但是并确很慢
常规实现思路
将每一个元素，看做是一个节点。
每个元素拥有一个指向父节点的指针。然后最上面的父节点指针指向自己。
Quick Union
parent(i) = i;
union 3 4
union 3 8
union 6 5
union 9 4
要将9连接到4的根节点8上去。数组中：4-3-8-8 8是4的根节点。9指向8.
4和9连接在一起：因为根相同。
其中6和2连接是6的根0和2的根1选取了1将0挂上。
namespace UF2{ class UnionFind{ private: int* parent; int count; public: UnionFind(int count){ parent = new int[count]; this->count = count; for( int i = 0 ; i < count ; i ++ ) parent[i] = i; } ~UnionFind(){ delete[] parent; } //不断向上找父亲 int find(int p){ assert( p >= 0 && p < count ); while( p != parent[p] ) p = parent[p]; return p; } //看是否能找到同样的根 bool isConnected( int p , int q ){ return find(p) == find(q); } //找到p的根，和q的根 void unionElements(int p, int q){ int pRoot = find(p); int qRoot = find(q); if( pRoot == qRoot ) return; //把根挂到另一个的根 parent[pRoot] = qRoot; } };} 运行结果：
当n大的时候，方法1更优了。
问题：
union 9,4 & union 4 9
9的元素少，将它指向4的根节点。形成的树层数低。
// 我们的第三版Union-Findnamespace UF3{ class UnionFind{ private: int* parent; // parent[i]表示第i个元素所指向的父节点 int* sz; // sz[i]表示以i为根的集合中元素个数 int count; // 数据个数 public: // 构造函数 UnionFind(int count){ parent = new int[count]; sz = new int[count]; this->count = count; for( int i = 0 ; i < count ; i ++ ){ parent[i] = i; sz[i] = 1; } } // 析构函数 ~UnionFind(){ delete[] parent; delete[] sz; } // 查找过程, 查找元素p所对应的集合编号 // O(h)复杂度, h为树的高度 int find(int p){ assert( p >= 0 && p < count ); // 不断去查询自己的父亲节点, 直到到达根节点 // 根节点的特点: parent[p] == p while( p != parent[p] ) p = parent[p]; return p; } // 查看元素p和元素q是否所属一个集合 // O(h)复杂度, h为树的高度 bool isConnected( int p , int q ){ return find(p) == find(q); } // 合并元素p和元素q所属的集合 // O(h)复杂度, h为树的高度 void unionElements(int p, int q){ int pRoot = find(p); int qRoot = find(q); if( pRoot == qRoot ) return; // 根据两个元素所在树的元素个数不同判断合并方向 // 将元素个数少的集合合并到元素个数多的集合上 if( sz[pRoot] < sz[qRoot] ){ parent[pRoot] = qRoot; sz[qRoot] += sz[pRoot]; } else{ parent[qRoot] = pRoot; sz[pRoot] += sz[qRoot]; } } };} 运行结果：
优化相当明显。
int main() { // 使用10000的数据规模 int n = 100000; // 虽然isConnected只需要O(1)的时间, 但由于union操作需要O(n)的时间 // 总体测试过程的算法复杂度是O(n^2)的 UnionFindTestHelper::testUF1(n); // 对于UF2来说, 其时间性能是O(n*h)的, h为并查集表达的树的最大高度 // 这里严格来讲, h和logn没有关系, 不过大家可以简单这么理解 // 我们后续内容会对h进行优化, 总体而言, 这个h是远小于n的 // 所以我们实现的UF2测试结果远远好于UF1, n越大越明显:) UnionFindTestHelper::testUF2(n); // 对于UF3来说, 其时间性能依然是O(n*h)的, h为并查集表达的树的最大高度 // 但由于UF3能更高概率的保证树的平衡, 所以性能更优 UnionFindTestHelper::testUF3(n); return 0;} 100万在1秒之内
依靠集合的size来决定谁指向谁并不完全合理。根据层数才最合理
基于rank的优化
namespace UF4{ class UnionFind{ private: int* rank; // rank[i]表示以i为根的集合所表示的树的层数 int* parent; // parent[i]表示第i个元素所指向的父节点 int count; // 数据个数 public: // 构造函数 UnionFind(int count){ parent = new int[count]; rank = new int[count]; this->count = count; for( int i = 0 ; i < count ; i ++ ){ parent[i] = i; rank[i] = 1; } } // 析构函数 ~UnionFind(){ delete[] parent; delete[] rank; } // 查找过程, 查找元素p所对应的集合编号 // O(h)复杂度, h为树的高度 int find(int p){ assert( p >= 0 && p < count ); // 不断去查询自己的父亲节点, 直到到达根节点 // 根节点的特点: parent[p] == p while( p != parent[p] ) p = parent[p]; return p; } // 查看元素p和元素q是否所属一个集合 // O(h)复杂度, h为树的高度 bool isConnected( int p , int q ){ return find(p) == find(q); } // 合并元素p和元素q所属的集合 // O(h)复杂度, h为树的高度 void unionElements(int p, int q){ int pRoot = find(p); int qRoot = find(q); if( pRoot == qRoot ) return; // 根据两个元素所在树的元素个数不同判断合并方向 // 将元素个数少的集合合并到元素个数多的集合上 if( rank[pRoot] < rank[qRoot] ){ parent[pRoot] = qRoot; } else if( rank[qRoot] < rank[pRoot]){ parent[qRoot] = pRoot; } else{ // rank[pRoot] == rank[qRoot] parent[pRoot] = qRoot; rank[qRoot] += 1; // 此时, 我维护rank的值 } } };} // 对于UF3来说, 其时间性能依然是O(n*h)的, h为并查集表达的树的最大高度 // 但由于UF3能更高概率的保证树的平衡, 所以性能更优 UnionFindTestHelper::testUF3(n); // UF4虽然相对UF3进行有了优化, 但优化的地方出现的情况较少, // 所以性能更优表现的不明显, 甚至在一些数据下性能会更差 UnionFindTestHelper::testUF4(n);
前面我们都在优化union。其实Find我们也可以进行优化。
我们要find4
4去连接它爷爷。下面考查2.
int find(int p){ assert( p >= 0 && p < count ); // path compression 1 while( p != parent[p] ){ parent[p] = parent[parent[p]]; p = parent[p]; } } 写一个递归的函数：调用findx，返回的就是x节点的根。让每个parentx指向findx的结果。findx的结果也是Findparentx的结果。找x的时候，将x的Findparent的结果，指向父亲的结果。
代码：
// path compression 2, 递归算法 if( p != parent[p] ) parent[p] = find( parent[p] ); return parent[p];
优化情况并不明显。甚至因为递归的消耗，。所以理论最优不一定实际好。
并查集的操作，时间复杂度近乎是O(1)的。
- 经过路径压缩：近乎1就能到根节点。解决图，网络连接。最短路径。路径是什么？都得使用图论。
转载地址：http://udall.baihongyu.com/