quick-find、quick-union、加權quick-union(附帶路徑壓縮優(yōu)化)

本算法主要解決動態(tài)連通性一類問題，這里盡量用精煉簡潔的話來闡述。

數(shù)據(jù)結構描述:

• 有N個節(jié)點（索引0~N-1），可以查詢節(jié)點數(shù)量
• 可以連接兩個節(jié)點
• 可以查詢兩個節(jié)點是否連通

算法大致設計思路：

• 每個節(jié)點初始化為不同的整數(shù)標記
• 通過一個輔助函數(shù)查詢某個節(jié)點的標記值
• 如果兩節(jié)點標記相同，說明兩節(jié)點是連通的

抽象基類：

class UnionFind
{
public:
    UnionFind(int n);
    ~UnionFind();
    int Count();
    virtual bool Connected(int p,int q)=0;
    virtual void Union(int p,int q)=0;
protected:
    int *id;
    int sz;
    int num;
};
UnionFind::UnionFind(int n)
{
    this->num = this->sz = n;
    this->id = new int[n];
    for(int i=0; i<n; i++)
    {
        this->id[i] = i;
    }
};
UnionFind::~UnionFind()
{
    delete this->id;
    delete &this->num;
    delete &this->sz;
};

int UnionFind::Count()
{
    return this->num;
};

QuickFind

• a和b進行union的時候，將b及與b連通節(jié)點的標記都置為和a的標記一樣
• 標記相同的節(jié)點是連通的

class QuickFind : public UnionFind
{
public:
    QuickFind(int n);
    bool Connected(int p,int q);
    void Union(int p,int q);
};
QuickFind::QuickFind(int n):UnionFind(n) {};


bool QuickFind::Connected(int p,int q)
{
    return this->id[p] == this->id[q];
};

void QuickFind::Union(int p,int q)
{
    int k = this->id[q];
    for(int i=0; i<this->sz; i++)
    {
        if(this->id[i]==k)
        {
            this->id[i]=this->id[p];
        }
    }
    this->num--;
};

QuickUnion

• 連通的節(jié)點形成一棵樹，根節(jié)點相同

class QuickUnion : public UnionFind
{
public:
    QuickUnion(int n);
    bool Connected(int p,int q);
    void Union(int p,int q);
protected:
    int findRoot(int p);
};
QuickUnion::QuickUnion(int n):UnionFind(n) {};
int QuickUnion::findRoot(int p)
{
    while(p!=this->id[p])
    {
        p = this->id[p];
    }
    return p;
};
bool QuickUnion::Connected(int p,int q)
{
    return this->findRoot(p)==this->findRoot(q);
};
void QuickUnion::Union(int p,int q)
{
    int i = this->findRoot(p);
    int j = this->findRoot(q);
    if (i == j)
    {
        return;
    }
    this->id[j] = this->id[i];
    this->num--;
};

加權QuickUnion(附帶路徑壓縮優(yōu)化)

• union的時候小樹掛在大樹下
• 查詢根節(jié)點的時候順便將該節(jié)點的父節(jié)點直接指向根節(jié)點，壓縮路徑

class WeightedQuickUnion : public QuickUnion
{
public:
    WeightedQuickUnion(int n);
    ~WeightedQuickUnion();
    void Union(int p,int q);
protected:
    int findRoot(int p);
private:
    int *sz;
};
WeightedQuickUnion::WeightedQuickUnion(int n):QuickUnion(n)
{
    this->sz = new int[n];
    for(int i=0; i<n; i++)
    {
        this->sz[i] = 1;
    }
};
WeightedQuickUnion::~WeightedQuickUnion()
{
    delete this->sz;
};
int WeightedQuickUnion::findRoot(int p)
{
    while (p != this->id[p])
    {
        this->id[p] = this->id[this->id[p]];
        p = this->id[p];
    }
    return p;
};
void WeightedQuickUnion::Union(int p,int q)
{
    int i = this->findRoot(p);
    int j = this->findRoot(q);
    if (i == j)
    {
        return;
    }
    if (this->sz[i] < this->sz[j])
    {
        this->id[i] = j;
        this->sz[j] += this->sz[i];
    }
    else
    {
        this->id[j] = i;
        this->sz[i] += this->sz[j];
    }
    this->num--;
};