C++中的最小生成樹算法超詳細教程

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

這篇文章主要介紹了C++中的最小生成樹算法超詳細教程,最小生成樹的最著名的算法有兩個, 一個是Prim算法, 另一個當然就是Kruskal算法, 接下來, 我將盡我所能的介紹這兩個算法, 也算是對自己學習的一個回顧吧,需要的朋友可以參考下

前言

最小生成樹的最著名的算法有兩個, 一個是 Prim 算法, 另一個當然就是 Kruskal 算法, 接下來, 我將盡我所能的介紹這兩個算法, 也算是對自己學習的一個回顧吧

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

題目背景

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

題目描述

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

你將得到一份各農(nóng)場之間連接費用的列表，你必須找出能連接所有農(nóng)場并所用光纖最短的方案。每兩個農(nóng)場間的距離不會超過105。

輸入格式

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

接下來是一個N×N的矩陣，表示每個農(nóng)場之間的距離。理論上，他們是N行，每行由N個用空格分隔的數(shù)組成，實際上，由于每行8080個字符的限制，因此，某些行會緊接著另一些行。當然，對角線將會是00，因為不會有線路從第i個農(nóng)場到它本身。

輸出格式

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

輸入輸出樣例

輸入 #1

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

輸出 #1

28

Kruskal 算法

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

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

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

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

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

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

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

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

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

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

struct Edge {
    int u; //起點
    int v; //終點
    int w; //權值
} e[100010];

對于并查集的處理就簡單的提一下

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.合并操作, 將兩個屬于不同集合的頂點合并到同一個集合, 即入贅操作

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

感覺也沒多少東西, 那就直接貼完整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;
}
//這一題應該采用并查集來判斷是否會構成一個環(huán), 然后用一個結構體數(shù)組來存儲邊的信息
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 算法也是一個貪心算法, 它和 Kruskal 算法的區(qū)別在于 Prim 算法是每次從一個點出發(fā)選擇當前點的不構成環(huán)的最小的邊, 而 Kruskal 算法是從全局的角度, 從所有的邊中選擇不構成環(huán)的最小的邊, 所以 Prim 算法相對而言復雜一些很顯然, 每次都要從當前的頂點選擇最優(yōu)的邊, 那么這就是一個很耗時的操作, 于是我們可以對這一步進行堆優(yōu)化(其實就是使用優(yōu)先隊列 ) 這個算法的數(shù)據(jù)結構相對復雜一些, 接下來我來介紹一下

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

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為起始點, 將其相連邊入隊

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)訪問過了
        continue;
    }
    vis[v] = true;
    ans += w; //ans是結果
    cnt++; //cnt是邊的計數(shù)器
    for (int i = 0; i < g[v].size(); i++) {
        if (!vis[g[v][i].v]) {
            edge.push(g[v][i]);
        }
    }
}

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

您可能感興趣的文章: