连接问题

网络中节点间的连接状态； 网络是个抽象的概念：用户之间形成的网络

路径问题

路径问题回答的更多；

并查集

对于一组数据，主要支持两个动作： union(p,q)合并 find(p )查找 用来回答一个问题： isConnected(p,q)连接 mian.cpp

#include <iostream> #include "UnionFindTestHelper.h" using namespace std; int main() { int n = 10000; UnionFindTestHelper::testUF1(n); return 0; }

UnionFind1.h

#ifndef INC_02_QUICK_FIND_UNIONFIND1_H #define INC_02_QUICK_FIND_UNIONFIND1_H #include <iostream> #include <cassert> using namespace std; 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; //每个元素id等于i } //析构函数 ~UnionFind() { delete[] id; } //查找操作 int find(int p) { //传入值 assert(p >= 0 && p < count); //确保 return id[p]; //直接返回id值 } bool isConnected(int p, int q) { return find(p) == find(q); } //union函数 void unionElements(int p, int q) { // 找到id int pID = find(p); int qID = find(q); //比较id if (pID == qID) return; //遍历，最后使p和q连接的组一样，最后p和q相连 for (int i = 0; i < count; i++) if (id[i] == pID) id[i] = qID; } }; } #endif //INC_02_QUICK_FIND_UNIONFIND1_H

帮助测试上面写的类 UnionFindTestHelper.h

// // Created by liuyubobobo on 9/2/16. // #ifndef INC_02_QUICK_FIND_UNIONFINDTESTHELPER_H #define INC_02_QUICK_FIND_UNIONFINDTESTHELPER_H #include <iostream> #include <ctime> #include "UnionFind1.h" using namespace std; namespace UnionFindTestHelper{ 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); } for(int i = 0 ; i < n ; i ++ ){ int a = rand()%n; int b = rand()%n; uf.isConnected(a,b); } time_t endTime = clock(); cout<<"UF1, "<<2*n<<" ops, "<<double(endTime-startTime)/CLOCKS_PER_SEC<<" s"<<endl; } } #endif //INC_02_QUICK_FIND_UNIONFINDTESTHELPER_H

将每一个元素，看作是一个节点； 每个节点都有一个指向父节点的指针，根节点指向自己

UnionFind2.h

// // Created by liuyubobobo on 9/2/16. // #ifndef INC_03_QUICK_UNION_UNIONFIND2_H #define INC_03_QUICK_UNION_UNIONFIND2_H #include <cassert> using namespace std; 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不断向上直到成为根节点 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; .//不相等则把一个作为另一个的根 } }; } #endif //INC_03_QUICK_UNION_UNIONFIND2_H

优化：合并的时候，为了保证树的高度最小，使数量少的指向数量多的，而不是固定的 UnionFind3.h

// // Created by liuyubobobo on 9/2/16. // #ifndef INC_04_OPTIMIZE_BY_SIZE_UNIONFIND3_H #define INC_04_OPTIMIZE_BY_SIZE_UNIONFIND3_H #include <cassert> using namespace std; namespace UF3{ class UnionFind{ private: int* parent; 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; } 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); } 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]; //维护sz数组 } else{ parent[qRoot] = pRoot; sz[pRoot] += sz[qRoot]; } } }; } #endif //INC_04_OPTIMIZE_BY_SIZE_UNIONFIND3_H

上面的优化有局限性：即使元素个数少的指向多的，最后的层数有可能会更高，现在加入rank作为新的标准

// // Created by liuyubobobo on 9/2/16. // #ifndef INC_05_OPTIMIZE_BY_RANK_UNIONFIND3_H #define INC_05_OPTIMIZE_BY_RANK_UNIONFIND3_H #include <cassert> using namespace std; namespace UF3{ class UnionFind{ private: int* parent; int* rank; // rank[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; //默认的层数为1 } } ~UnionFind(){ delete[] parent; delete[] rank; } 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); } void unionElements(int p, int q){ int pRoot = find(p); int qRoot = find(q); if( pRoot == qRoot ) return; if( rank[pRoot] < rank[qRoot] ){ //比较p和q的层数，如果p的层数小，则p指向q parent[pRoot] = qRoot; //不需要对rank进行维护 } else if( rank[qRoot] < rank[pRoot]){ parent[qRoot] = pRoot; } else{ // rank[pRoot] == rank[qRoot] parent[pRoot] = qRoot; //制定p指向q，则q的rank加1 rank[qRoot] += 1; //两者相等的时候层数一定会增加，此时维护rank要加1 } } }; } #endif //INC_05_OPTIMIZE_BY_RANK_UNIONFIND3_H

路径压缩优化 之前只是简单的组装，现在考虑使用路径压缩的方式（节点考察父节点是否还有父节点，如果有的话则这个节点直接连接爷节点；下一步再考虑原来节点的父节点，直接进行了跳跃）最后使得层数大大的减少。

#include <iostream> #include "UnionFind5.h" using namespace std; int main() { UF5::UnionFind uf = UF5::UnionFind(5); uf.unionElements(1,0); uf.unionElements(2,1); uf.unionElements(3,2); uf.unionElements(4,3); uf.show(); cout<<"======"<<endl; uf.find(4); uf.show(); return 0; }

UnionFind4.h

// // Created by liuyubobobo on 8/31/16. // #ifndef UNIONFIND_UNIONFIND4_H #define UNIONFIND_UNIONFIND4_H #include <cassert> using namespace std; // Quick Union + rank namespace UF4{ class UnionFind{ private: int* parent; int* rank; // rank[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; } int size(){ return count; } bool isConnected( int p , int q ){ return find(p) == find(q); } int find(int p){ assert( p >= 0 && p < count ); // while( p != parent[p] ) // p = parent[p]; // return p; // } //递归式路径压缩：如果p不是根节点，将p的父节点指向根节点 if ( p ! = parent[p]) parent[p] = find( parent[p]); return parent[p]; } 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] ++; } } }; } #endif //UNIONFIND_UNIONFIND4_H

UnionFind5.h

// // Created by liuyubobobo on 8/31/16. // #ifndef UNIONFIND_UNIONFIND5_H #define UNIONFIND_UNIONFIND5_H #include <cassert> using namespace std; // Quick Union + rank + path compression namespace UF5{ class UnionFind{ private: int* parent; int* rank; 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; } int size(){ return count; } bool isConnected( int p , int q ){ return find(p) == find(q); } int find(int p){ assert( p >= 0 && p < count ); // path compression 1 while( p != parent[p] ){ //************************************************************** parent[p] = parent[parent[p]]; //当p不是根节点，就使p指向p的爷节点 //************************************************************** p = parent[p]; //然后继续使p指向p的父节点 } return p; // path compression 2 // if( p != parent[p] ) // parent[p] = find( parent[p] ); // return parent[p]; } 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] ++; } } void show(){ for( int i = 0 ; i < count ; i ++ ) cout<<i<<" : "<<parent[i]<<endl; } }; } #endif //UNIONFIND_UNIONFIND5_H