并查集详解和STL中的自定义哈希

算法工程师之路

发布于 2019-08-05 20:22:59

1.3K0

发布于 2019-08-05 20:22:59

今天我们要介绍一种简单但对于合并和查找都十分高效的结构——并查集，其底层实现也十分简单，并且应用非常广泛，比如最小生成树算法中的Kruskal算法，里面有使用了并查集的结构！并且在并查集结构为了加速查找，底层使用基于hash的容器，在CPP中，叫做unordered_map! unordered_map是C++11标准的东西，其为基础类型提供了hash模板，但是如果自定义类型呢？我们如何去构建这个容器？下面会给你答案！

Unordered_map（自定义类型）

在STL库中，我们要注意区别map和unordered_map以及set和unordered_set，其中map和set底层数据结构为红黑树，且为关联容器且按照关键字有序的保存元素，而另外两个其底层数据结构为哈希函数所组织的，查找效率为O(1)。

由于在STL中，有关于hash的数据结构值针对于基础数据类型如int, string等提供了hash模板，因此如果想要使用自定义类，那么我们需要重写仿函数，也就是自定义hash函数！一般来说，我们需要重写以下两个函数： 注意：重写的两个函数为常函数，一定不要忘了加const

// hash函数
size_t operator()(const Key& k) const{
    ...
}
// 判断键值是否相等
bool operator()(const Key& k1, const Key& k2){
    ...
}

接下来我们看一个自定义类型使用unordered_map的例子，而另外一个unordered_set的重写方式是一样的，大家自己可以去试一试！在这里我们使用自定义类型为Key，然后分别使用sturct建立仿函数，重写hash函数和equal_to函数！！！然后就可以愉快的使用啦！

#include <unordered_map>
#include <string>
#include <iostream>

using namespace std;

struct Key{
    string first;
    string second;
    Key(string first, string second){
        this->first = first;
        this->second = second;
    }
};

struct KeyHash{
    size_t operator()(const Key& k) const{
        return hash<string>()(k.first) ^
        (hash<string>()(k.second) << 1);
    }
};

struct KeyEqual{
    bool operator()(const Key& lhs, const Key& rhs) const{
        return lhs.first == rhs.first && lhs.second == rhs.second;
    }
};

int main(int argv, char** argc){
    unordered_map<Key, string, KeyHash, KeyEqual> m = {
        {{"teddy", "zhang"}, "example"},
        {{"mary", "sue"}, "another"}
    };
    Key a("teddy", "zhang");
    cout << m[a] << endl;
    for(auto s: m){
        cout << s.second << endl;
    }
}

并查集

并查集的结构非常简单，但是很有实用性，在大量数据平均情况下，查找的复杂度可以为O(1)，其原理如下：首先我们将一个序列的每个元素都当做一个集合，同时将这个元素标记为这个集合的代表节点，那么如何标记呢？很简单，其父节点是自己的节点就叫做代表节点！因此，我们在并查集机构中使用hash_map(也就是STL中的unordered_map)来进行信息储存，key表示当前节点，value表示父节点！然后我们还要建立另一个hash_map用来保存集合的大小的信息，key表示节点，value表示当前节点所在集合中的节点总数！

注意：节点总数的信息只对代表节点有效，其他节点这个信息是无效的！并且这个并查集结构对外调用的方法有三个，分别是：

findRep() 查找代表节点
Union() 合并两个集合，合并时小集合会合并到大集合下，总的代表节点为大集合的代表节点
isSameSet() 用来判断两个集合是不是在同一个集合下

合并两个集合：

合并时，集合小的代表节点会直接挂在集合大的代表节点下，从而完成合并！

并查集合并两集合

查找代表节点：

一定要注意，这是并查集的核心功能，在查找代表节点时，会使用递归的方式，比如下方图中，当查找元素8的代表节点时，会不停的判断当前节点和其父节点是不是同一个节点，如果是，则找到代表节点1，由于是一个递归的过程，在找到代表节点后，将所有遍历过的节点的父节点都设置为代表节点，因此就将链表压平了！等下次查找时候就会快很多，不用再遍历那么多的节点了！

并查集查找策略（核心）

由于上述的操作都是建立在hash函数的组织之下，因此效率非常高，速度也非常快！并且代码量也不多，主要就是查找函数中的递归算法，一定要理解清楚！

#include <hash_map>
#include <iostream>
#include <vector>

using namespace std;

using namespace __gnu_cxx;  // linux下使用，window请注释

// 只有每个集合的代表节点是自己指向自己的，这也是并查集的特殊节点唯一标示
class UnionFindSet{
private:
    hash_map<char, char> father;   // value表示父节点
    hash_map<char, int> size;
public:
    UnionFindSet(vector<char> data){
        father.clear();
        size.clear();
        for(auto var : data){
            father.insert({var, var});
            size.insert({var, 1});
        }
    }

    char findRep(char node){
        char f = father[node];
        if (f != node){
            f = findRep(f);
        }
        father[node] = f;
        return f;
    }

    bool isSameSet(char a, char b){
        return findRep(a) == findRep(b);
    }

    void Union(char a, char b){
        char aRep = findRep(a);
        char bRep = findRep(b);
        if(aRep != bRep){
            int aSize = size[aRep];
            int bSize = size[bRep];
            if(aSize > bSize){
                father[b] = a;
                size[a] += size[b];
            }
            else{
                father[a] = b;
                size[b] += size[a];
            }
        }
    }
};

int main(int argc, char** argv){
    vector<char> tmp = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'};
    UnionFindSet s(tmp);
    s.Union('A', 'B');
    cout << s.isSameSet('A', 'B') << endl;  
}