C++怎么實(shí)現(xiàn)基于不相交集合的kruskal算法

這篇文章主要介紹“C++怎么實(shí)現(xiàn)基于不相交集合的kruskal算法”，在日常操作中，相信很多人在C++怎么實(shí)現(xiàn)基于不相交集合的kruskal算法問(wèn)題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”C++怎么實(shí)現(xiàn)基于不相交集合的kruskal算法”的疑惑有所幫助！接下來(lái)，請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧！

C++實(shí)現(xiàn)基于不相交集合的O(mlgn)復(fù)雜度的kruskal算法

不相交集合的數(shù)據(jù)結(jié)構(gòu)

我們采用森林的方式實(shí)現(xiàn)不相交集合。這個(gè)森林是極簡(jiǎn)化的,每個(gè)節(jié)點(diǎn)只有一個(gè)指向父親的指針,而且森林中的每一顆樹都是一個(gè)集合,我們?nèi)涞母?jié)點(diǎn)為這個(gè)集合的代表元。

int rank[505];
int father[505];
void make_set(int x)
{
	father[x]=x;
	rank[x]=0;
}
int find_set(int x)
{
    if (x!=father[x])
    {
        father[x]=find_set(father[x]);
    }
    return father[x];
}
void simply_union_set(int u,int v)
{
    u=find_set(u);
    v=find_set(v);
    father[u]=v;
}
void  perfect_union_set(int u,int v)
{
    u=find_set(u);
    v=find_set(v);
    if (rank[u]>rank[v])
    {
        father[v]=u;
    }
    else
    {
        father[u]=v;
        if(rank[u]==rank[v])
        rank[v]++;
    }

}

可以看到在find_set()函數(shù)中采用了兩趟遍歷的思想,第一趟遍歷找的根節(jié)點(diǎn),第二趟遍歷將路徑上的節(jié)點(diǎn)全部指向根節(jié)點(diǎn),完成了壓縮樹高。

在實(shí)現(xiàn)集合合并的時(shí)候,我們采用了兩種方法:一種方法是直接合并simply_union_set,另一種是采用按秩合并的思想perfect_union_set,即總是讓秩小合并到秩大的集合中,這是一種減少樹高的有效策略;

當(dāng)我們采用按秩合并時(shí)時(shí),上述每一個(gè)操作的最差時(shí)間復(fù)雜度,都約等于O(1)

kruskal 算法

void kruskal()
{
    for(int i=0;i<num_v;i++)make_set(i);
    sort(arr_edge.begin(),arr_edge.end(),mycompare);
    for(int i=0;i<arr_edge.size();i++)
    {
        int fr=arr_edge[i].fr;
        int to=arr_edge[i].to;
        int w=arr_edge[i].w;
        if( find_set(fr)!=find_set(to))
        {
        	result+=w;
            perfect_union_set(fr,to);
        }
    }
}

kruskal 算法是一種基于貪心策略的算法,它的時(shí)間復(fù)雜度的最大開銷就是排序算法,即O(mlgm)=O(mlgn),這里m表示邊數(shù),n表示頂點(diǎn)數(shù)

知識(shí)補(bǔ)充

乘勝追擊一下，通過(guò)一個(gè)例題再深入了解一下kruskal 算法吧

思路：就是最小生成樹啊

代碼

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
#define INTMAX 0x3f3f3f3f
typedef pair<int,int> pii;
typedef long long ll;
#define x first
#define y second

int rank[505];
int father[505];
int find_set(int x)
{
    if (x!=father[x])
    {
        father[x]=find_set(father[x]);
    }
    return father[x];
}
void simply_union_set(int u,int v)
{
    u=find_set(u);
    v=find_set(v);
    father[u]=v;
}
void  perfect_union_set(int u,int v)
{
    u=find_set(u);
    v=find_set(v);
    if (rank[u]>rank[v])
    {
        father[v]=u;
    }
    else
    {
        father[u]=v;
        if(rank[u]==rank[v])
        rank[v]++;
    }

}
struct edge
{
    int fr,to,w;
};
int num_case,num_v,result;
vector<edge> arr_edge;

void debug()
{
    for(int i=0;i<arr_edge.size();i++)
    {
        cout<<arr_edge[i].fr<<" to "<<arr_edge[i].to<<"="<<arr_edge[i].w<<endl;
    }
}

void init()
{
    arr_edge.clear();
    result=0;
}
void input()
{
    int w;
    scanf("%d",&num_v);
    for(int i=0;i<num_v;i++)
    {
        for(int j=0;j<num_v;j++)
        {
            scanf("%d",&w);
            if(i<j)
            {
                edge temp;
                temp.fr=i;
                temp.to=j;
                temp.w=w;
                arr_edge.push_back(temp);
            }
        }
    }

}
bool mycompare(const edge& x,const edge &y)
{
    return x.w<y.w;
}
void kruskal()
{
    for(int i=0;i<num_v;i++)father[i]=i;
    sort(arr_edge.begin(),arr_edge.end(),mycompare);
    for(int i=0;i<arr_edge.size();i++)
    {
        int fr=arr_edge[i].fr;
        int to=arr_edge[i].to;
        int w=arr_edge[i].w;
        if( find_set(fr)!=find_set(to))
        {
            result=max(result,w);
            simply_union_set(fr,to);
        }
    }
}
void solve()
{
    init();
    input();
    //debug();
    kruskal();
    cout<<result<<endl;
}

int main()
{
    scanf("%d",&num_case);
    while(num_case--)
    {
        solve();
    }
    return 0;
}

到此，關(guān)于“C++怎么實(shí)現(xiàn)基于不相交集合的kruskal算法”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！