图的并查集QuickFind类总结——C++

图分为无向图、有向图、加权图。其中理解图论中一个重要概念是并查集。并查集有两个重要功能，分别是find查找根节点函数和union连通两个节点。传统的并查集实现算法效率较低，引申出两种优化版的并查集算法，分别是QuickFind类和UnionFind，本文主要介绍QuickFind类的实现。

一、类QuickFind介绍

1.1 类QuickFind功能和函数

类QuickFind主要有两个重要函数，分别是findRoot()和unionNode()。

函数findRoot()功能是查找某个节点的根节点

函数unionNode()功能是连通两个节点，代码实现上是将两个节点的根节点标志为一个共同根节点

1.2代码实现思路

a1 先初始化root数组，数组下标为节点，数组值为节点父节点或根节点

QuickFind(int size)
{
    root.resize(size);
    for (int i = 0; i < size; ++i)
        root[i] = i;
}

a2 实现findRoot(int n)函数，查找函数中，root数组的值为对应节点的根节点

int findRoot(int n) const
{
    return root[n];
}

a3 实现unionNode(int x, int y)函数，查找两个节点x,y的根节点，如果不同，则遍历整个数组更新数组值为rootY的数组，即root[i] = rootX；

void unionNode(int x, int y)
{
    int rootX = findRoot(x);
    int rootY = findRoot(y);
    if (rootX != rootY)
    {
        for (int i = 0; i < root.size(); ++i)
        {
            if (root[i] == rootY)
                root[i] = rootX;
        }
    }
}

1.2完整代码实现

class QuickFind
{
public:
    QuickFind(int size)
    {
        root.resize(size); // 初始化size个节点
        for (int i = 0; i < size; ++i) 
            root[i] = i; // 节点下标即为父节点值，即根节点的父节点是自身
    }

    int findRoot(int n) const
    {
        return root[n]; // 时间复杂度O(1)
    }

    void unionNode(int x, int y)
    {
        int rootX = findRoot(x);
        int rootY = findRoot(y);
        if (rootX != rootY) // 如果两个节点根节点不同，则更新为相同根节点
        {
            for (int i = 0; i < root.size(); ++i) // 更新所有根节点值为rootY的节点
            {
                if (root[i] == rootY)
                    root[i] = rootX;
            }
        }
    }

private:
    vector<int> root;
};