并查集路径压缩优化 UnionFind PathCompression(C++)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了并查集路径压缩优化 UnionFind PathCompression(C++)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2282字，纯文字阅读大概需要4分钟。

内容图文

/*
 * UnionFind.h
 * 有两种实现方式,QuickFind和QuickUnion
 * QuickFind:
 *          查找O(1)
 *          合并O(n)
 * QuickUnion：(建议使用)
 *          查找O(logn)可优化至O(a(n)),a(n)<5
 *          合并O(logn)可优化至O(a(n)),a(n)<5
 *  Created on: 2020年2月13日
 *      Author: LuYonglei
 */

//由于QuickFind平均时间复杂度不理想，所以本文件只用QuickUnion来实现
//本文件基于rank实现优化
//在原有基础上实现路径压缩
#ifndef SRC_UNIONFIND_H_
#define SRC_UNIONFIND_H_
#include <assert.h>
#include <stack>
#define DEFAULT_CAPACITY 10
using namespace std;

class UnionFind {
public:
    UnionFind(int capacity) :
            capacity_(capacity > 0 ? capacity : DEFAULT_CAPACITY), parents(
                    new int[capacity > 0 ? capacity : DEFAULT_CAPACITY]), ranks(
                    new int[capacity > 0 ? capacity : DEFAULT_CAPACITY]) {
        //初始化构造函数
        for (int i = 0; i < capacity_; i++) {
            parents[i] = i;
            ranks[i] = 1; //以i为根节点的树的高度
        }
    }

    ~UnionFind() {
        //析构函数
        delete[] parents;
        delete[] ranks;
    }

#if 0
    //递归实现路径压缩
    int findParent(int value) {
        assert(value < capacity_ && value >= 0);
        if (parents[value] != value) {
            parents[value] = findParent(parents[value]);
        }
        return parents[value];
    }
#elif 0
    //迭代实现路径压缩1
    int findParent(int value) {
        assert(value < capacity_ && value >= 0);
        stack<int> s;
        while (value != parents[value]) {
            s.push(value);
            value = parents[value];
        }
        int preIndex = 0;
        while (s.size() != 0) {
            preIndex = s.top();
            parents[preIndex] = value;
            s.pop();
        }
        return value;
    }

#else
    //迭代实现路径压缩2
    int findParent(int value) {
        assert(value < capacity_ && value >= 0);
        int begin = value;
        while (value != parents[value]) {
            value = parents[value];
        }
        int tmpBegin = 0;
        while (begin != value) {
            tmpBegin = parents[begin];
            parents[begin] = value;
            begin = tmpBegin;
        }
        return value;
    }

#endif

    void unionValue(int leftValue, int rightValue) {
        //统一实现左边跟随右边
        int leftParent = findParent(leftValue);
        int rightParent = findParent(rightValue);
        if (leftParent == rightParent)
            return;
        if (ranks[leftParent] < ranks[rightParent]) {
            parents[leftParent] = rightParent;
        } else if (ranks[rightParent] > ranks[leftParent]) {
            parents[rightParent] = leftParent;
        } else {
            parents[leftParent] = rightParent;
            ranks[rightParent] += 1;
        }
    }

    bool isSame(int leftValue, int rightValue) {
        return findParent(leftValue) == findParent(rightValue);
    }

private:
    int capacity_;
    int *parents;
    int *ranks;
};

#endif /* SRC_UNIONFIND_H_ */

内容总结

以上是互联网集市为您收集整理的并查集路径压缩优化 UnionFind PathCompression(C++)全部内容，希望文章能够帮你解决并查集路径压缩优化 UnionFind PathCompression(C++)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端