[数据结构与算法]最小生成树prim算法和kruskal算法模板

最小生成树真题可以康康这个：P3366 【模板】最小生成树 - 洛谷 | 计算机科学教育新生态

C站最小生成树两种算法详解文章各个都是精品，但是到了代码……未免长了点，注释也不明了。这篇文章再给出信息学奥赛书上的两种算法模板。

Prim算法

算法详解推荐文章：Prim算法_杨氏计算机知识整理-CSDN博客_prim算法

以下可能是最简题解：

#include <bits/stdc++.h>
using namespace std;

int g[101][101];  // 存放邻接矩阵
// minn[i]存放未加入最小生成树的点与任意已加入生成树的点路径权值的最小值
int minn[101];
bool u[101];  // u[i]=true表示i已加入生成树

int main() {
    int n;
    memset(minn, 0x7f7f7f7f, sizeof(minn));  // 初始化为最大值
    minn[1] = 0;  // 起点赋0值，即默认从起点开始

    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) cin >> g[i][j];  // 输入邻接矩阵

    for (int i = 1; i <= n; i++) {
        int k = 0;  // minn[0]始终为最大值，方便找最小值
        for (int j = 1; j <= n; j++) {
            if (!u[j] && (minn[j] < minn[k])) k = j;
        }
        u[k] = true;  // k加入最小生成树

        for (int j = 1; j <= n; j++) {
            // 未加入最小生成树且与新加入的k点相邻的点，通过g[k][j]更新minn[j]
            if (!u[j] && (g[k][j] < minn[j])) minn[j] = g[k][j];
        }
    }

    int tot = 0;
    for (int i = 1; i <= n; i++) tot += minn[i];
    cout << tot;

    return 0;
}

输入：

3
0 1 2
1 0 1
2 1 0 

输出：

2

输出解释：连接1和2、2和3，费用为2

Kruskal算法

Kruskal算法需要并查集知识，不了解的请看我这篇文章：算法刷题【洛谷P3367】并查集 - 模板_异想之旅的博客-CSDN博客

算法详解推荐文章：最小生成树之Kruskal算法_Enstein_Jun-CSDN博客_kruskal算法

代码还在赶来的路上……