1 基礎(chǔ)知識(shí)

kruskal算法的關(guān)鍵步驟為：

1. 將所有邊按照權(quán)重從小到大排序。
2. 定義集合S，表示生成樹。
3. 枚舉每條邊(a,b,c)，起點(diǎn)a，終點(diǎn)b，邊長c。如果結(jié)點(diǎn)a和結(jié)點(diǎn)b不連通（用并查集來維護(hù)），則將這條邊加入到集合S中。

kruskal算法的時(shí)間復(fù)雜度為O(mlogm)，它用來解決稀疏圖的最小生成樹問題。

2 模板

int n, m;       // n是點(diǎn)數(shù)，m是邊數(shù)
int p[N];       // 并查集的父節(jié)點(diǎn)數(shù)組

struct Edge     // 存儲(chǔ)邊
{
    int a, b, w;

    bool operator< (const Edge &W)const
    {
        return w < W.w;
    }
}edges[M];

int find(int x)     // 并查集核心操作
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal()
{
    sort(edges, edges + m);

    for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集

    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a = find(a), b = find(b);
        if (a != b)     // 如果兩個(gè)連通塊不連通，則將這兩個(gè)連通塊合并
        {
            p[a] = b;
            res += w;
            cnt ++ ;
        }
    }

    if (cnt < n - 1) return INF;
    return res;
}

3 工程化

題目1：求最小生成樹。文章來源地址http://www.zghlxwxcb.cn/news/detail-752521.html

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10;
int p[N];
int n, m;

struct Edge {
    int a, b, w;
    bool operator< (const Edge& W) const {
        return w < W.w;
    }
}edges[N];

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> edges[i].a >> edges[i].b >> edges[i].w;
    }
    
    //初始化并查集
    for (int i = 1; i <= n; ++i) p[i] = i;
    
    sort(edges, edges + m);
    
    int res = 0, cnt = 0;
    for (int i = 0; i < m; ++i) {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        a = find(a);
        b = find(b);
        if (a != b) {
            p[a] = b;
            res += w;
            cnt ++;
        }
    }
    
    if (cnt < n-1) {
        cout << "impossible" << endl;
    } else {
        cout << res << endl;
    }
    
    return 0;
}

到了這里，關(guān)于acwing算法基礎(chǔ)之搜索與圖論--kruskal算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！