快捷導(dǎo)航

C++中的最小生成樹(shù)算法超詳細(xì)教程

更新時(shí)間：2023年08月23日 09:56:59 作者：吃代碼的喵醬-i

這篇文章主要介紹了C++中的最小生成樹(shù)算法超詳細(xì)教程,最小生成樹(shù)的最著名的算法有兩個(gè), 一個(gè)是Prim算法, 另一個(gè)當(dāng)然就是Kruskal算法, 接下來(lái), 我將盡我所能的介紹這兩個(gè)算法, 也算是對(duì)自己學(xué)習(xí)的一個(gè)回顧吧,需要的朋友可以參考下

前言

最小生成樹(shù)的最著名的算法有兩個(gè), 一個(gè)是 Prim 算法, 另一個(gè)當(dāng)然就是 Kruskal 算法, 接下來(lái), 我將盡我所能的介紹這兩個(gè)算法, 也算是對(duì)自己學(xué)習(xí)的一個(gè)回顧吧

老規(guī)矩, 模板題如下

題目背景

Farmer John 被選為他們鎮(zhèn)的鎮(zhèn)長(zhǎng)！他其中一個(gè)競(jìng)選承諾就是在鎮(zhèn)上建立起互聯(lián)網(wǎng)，并連接到所有的農(nóng)場(chǎng)。當(dāng)然，他需要你的幫助。

題目描述

FJ 已經(jīng)給他的農(nóng)場(chǎng)安排了一條高速的網(wǎng)絡(luò)線(xiàn)路，他想把這條線(xiàn)路共享給其他農(nóng)場(chǎng)。為了用最小的消費(fèi)，他想鋪設(shè)最短的光纖去連接所有的農(nóng)場(chǎng)。

你將得到一份各農(nóng)場(chǎng)之間連接費(fèi)用的列表，你必須找出能連接所有農(nóng)場(chǎng)并所用光纖最短的方案。每?jī)蓚€(gè)農(nóng)場(chǎng)間的距離不會(huì)超過(guò)105。

輸入格式

第一行農(nóng)場(chǎng)的個(gè)數(shù)N（3 ≤ N ≤ 100)

接下來(lái)是一個(gè)N×N的矩陣，表示每個(gè)農(nóng)場(chǎng)之間的距離。理論上，他們是N行，每行由N個(gè)用空格分隔的數(shù)組成，實(shí)際上，由于每行8080個(gè)字符的限制，因此，某些行會(huì)緊接著另一些行。當(dāng)然，對(duì)角線(xiàn)將會(huì)是00，因?yàn)椴粫?huì)有線(xiàn)路從第i個(gè)農(nóng)場(chǎng)到它本身。

輸出格式

只有一個(gè)輸出，其中包含連接到每個(gè)農(nóng)場(chǎng)的光纖的最小長(zhǎng)度。

輸入輸出樣例

輸入 #1

4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0

輸出 #1

28

Kruskal 算法

首先, 介紹我更喜歡的, 也是相對(duì)更容易敲代碼的 Kruskal 算法

按照離散數(shù)學(xué)的定義

> 基本思想：按照權(quán)值從小到大的順序選擇n-1條邊，并保證這n-1條邊不構(gòu)成回路。

> 具體做法：首先構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)的森林，然后依權(quán)值從小到大從連通網(wǎng)中選擇邊加入到森林中，并使森林中不產(chǎn)生回路，直至森林變成一棵樹(shù)為止。

故我們可以提煉出算法的流程如下

將邊升序排序
判斷是否能插入此邊,插入后做:
- inc(ans,路徑長(zhǎng)度)
- 合并連通分支

1.對(duì)于排序, 可以借助于庫(kù)函數(shù)sort

2.對(duì)于判斷是否可以插入的步驟, 我們的想法是借助于并查集, 如果這條邊的兩個(gè)祖先相同, 那么插入這條邊顯然會(huì)構(gòu)成環(huán), 故跳過(guò)

3.算法結(jié)束的標(biāo)志是加入的邊的數(shù)目為n - 1

算法已經(jīng)介紹清楚了, 那么下面我們就來(lái)考慮一下存儲(chǔ)邊的數(shù)據(jù)結(jié)構(gòu), 我們選擇了如下所示的結(jié)構(gòu)體數(shù)組

struct Edge {
    int u; //起點(diǎn)
    int v; //終點(diǎn)
    int w; //權(quán)值
} e[100010];

對(duì)于并查集的處理就簡(jiǎn)單的提一下

1. 初始化

void init() {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
}

2.尋找祖先的函數(shù), 路徑壓縮算法

int find (int x) {
    return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
}

3.合并操作, 將兩個(gè)屬于不同集合的頂點(diǎn)合并到同一個(gè)集合, 即入贅操作

void union_(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    fa[fx] = fy;
}

感覺(jué)也沒(méi)多少東西, 那就直接貼完整AC代碼吧

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100 + 10;
int n, cnt, fa[MAXN], sum, ans;
void init() {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
}
int find (int x) {
    return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
}
void union_(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    fa[fx] = fy;
}
struct Edge {
    int u;
    int v;
    int w;
} e[100010];
bool cmp (Edge a, Edge b) {
    return a.w < b.w;
}
//這一題應(yīng)該采用并查集來(lái)判斷是否會(huì)構(gòu)成一個(gè)環(huán), 然后用一個(gè)結(jié)構(gòu)體數(shù)組來(lái)存儲(chǔ)邊的信息
int main() {
    cin >> n;
    init();
    int h;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> h;
            if (j > i) {
                //存一半就可以了
                e[++cnt].u = i;
                e[cnt].v = j;
                e[cnt].w = h;
            }
        }
    }
    sort(e + 1, e + 1 + cnt, cmp);
    for (int i = 1; i <= cnt; i++) {
        int u = e[i].u;
        int v = e[i].v;
        if (find(u) != find(v)) {
            union_(u, v);
            sum++;
            ans += e[i].w;
            if (sum == n - 1) {
                break;
            }
        }
    }
    cout << ans;
    return 0;
}

Prime 算法

Prim 算法也是一個(gè)貪心算法, 它和 Kruskal 算法的區(qū)別在于 Prim 算法是每次從一個(gè)點(diǎn)出發(fā)選擇當(dāng)前點(diǎn)的不構(gòu)成環(huán)的最小的邊, 而 Kruskal 算法是從全局的角度, 從所有的邊中選擇不構(gòu)成環(huán)的最小的邊, 所以 Prim 算法相對(duì)而言復(fù)雜一些很顯然, 每次都要從當(dāng)前的頂點(diǎn)選擇最優(yōu)的邊, 那么這就是一個(gè)很耗時(shí)的操作, 于是我們可以對(duì)這一步進(jìn)行堆優(yōu)化(其實(shí)就是使用優(yōu)先隊(duì)列 ) 這個(gè)算法的數(shù)據(jù)結(jié)構(gòu)相對(duì)復(fù)雜一些, 接下來(lái)我來(lái)介紹一下

bool vis[MAXN]; //用來(lái)判斷這個(gè)頂點(diǎn)是否訪(fǎng)問(wèn)過(guò)
struct Edge {
    int u; //起點(diǎn)
    int v; //終點(diǎn)
    int w; //權(quán)值
    bool operator <(const struct Edge& n) const {
        return w > n.w;
    } //重載比較運(yùn)算符, 用于后面的優(yōu)先隊(duì)列
};
vector <Edge> g[MAXN]; //向量數(shù)組, 用于存放每一個(gè)頂點(diǎn)所連接的邊的信息
priority_queue <Edge> edge; //優(yōu)先隊(duì)列不解釋

1.讀取數(shù)據(jù)

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        int w;
        cin >> w;
        if (w == 0) continue;
        g[i].push_back(Edge{i, j, w});
    }
}

2.以1為起始點(diǎn), 將其相連邊入隊(duì)

vis[1] = true;
for (int i = 0; i < g[1].size(); i++) {
    edge.push(g[1][i]);
}

3.執(zhí)行 Prim算法, 直到邊數(shù)為n - 1為止

 while (cnt < n - 1){
    int w = edge.top().w;
    int v = edge.top().v;
    edge.pop();
    if (vis[v]) {
        //已經(jīng)訪(fǎng)問(wèn)過(guò)了
        continue;
    }
    vis[v] = true;
    ans += w; //ans是結(jié)果
    cnt++; //cnt是邊的計(jì)數(shù)器
    for (int i = 0; i < g[v].size(); i++) {
        if (!vis[g[v][i].v]) {
            edge.push(g[v][i]);
        }
    }
}

到此這篇關(guān)于C++中的最小生成樹(shù)算法超詳細(xì)教程的文章就介紹到這了,更多相關(guān)C++中的最小生成樹(shù)算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: