最小生成树Kruskal算法（邻接矩阵和邻接表）

Kruskal算法是求解无向图的最小生成树（MST）问题的一种贪心算法。它的基本思想是将图中的边按照权值从小到大进行排序，然后依次加入到生成树中，如果加入该边不会形成环路，则将该边加入生成树中，否则舍弃该边。

Kruskal算法的实现有两种方式，一种是基于邻接矩阵的实现，一种是基于邻接表的实现。

1. 基于邻接矩阵的实现

首先，我们需要定义一个结构体 `Edge` 表示图中的一条边，包括起点、终点、权值三个属性。然后，我们将所有的边按照权值从小到大排序，依次遍历每条边，判断加入该边是否会形成环路，如果不会，则将该边加入生成树中。

代码实现如下：

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 100; // 最大顶点数
const int INF = 0x3f3f3f3f; // 表示正无穷

// 边的结构体
struct Edge {
    int u, v, w; // 起点、终点、权值
    bool operator<(const Edge& e) const {
        return w < e.w;
    }
} edges[MAXN * MAXN]; // 存储所有边的数组

int n, m; // 顶点数和边数
int parent[MAXN]; // 并查集数组，用于判断是否形成环路

// 并查集查找根节点
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

// Kruskal算法求解最小生成树
void kruskal() {
    int ans = 0; // 最小权值和
    for (int i = 1; i <= n; i++) {
        parent[i] = i; // 初始化并查集
    }
    sort(edges, edges + m); // 按照边权从小到大排序
    for (int i = 0; i < m; i++) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        int pu = find(u), pv = find(v);
        if (pu != pv) { // 不形成环路
            parent[pu] = pv; // 更新并查集
            ans += w; // 加入该边
        }
    }
    cout << "最小权值和为：" << ans << endl;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }
    kruskal();
    return 0;
}

2. 基于邻接表的实现

邻接表表示图的方法是将每个顶点的所有邻接点存储在一个链表中，因此我们需要定义一个结构体 `Node` 表示链表中的一个节点，包括邻接点和权值两个属性。然后，我们将所有的边按照权值从小到大排序，依次遍历每条边，判断加入该边是否会形成环路，如果不会，则将该边加入生成树中。

代码实现如下：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int MAXN = 100; // 最大顶点数
const int INF = 0x3f3f3f3f; // 表示正无穷

// 邻接表中的节点结构体
struct Node {
    int v, w; // 邻接点和权值
};

// 边的结构体
struct Edge {
    int u, v, w; // 起点、终点、权值
    bool operator<(const Edge& e) const {
        return w < e.w;
    }
} edges[MAXN * MAXN]; // 存储所有边的数组

int n, m; // 顶点数和边数
int parent[MAXN]; // 并查集数组，用于判断是否形成环路
vector<Node> adj[MAXN]; // 邻接表

// 并查集查找根节点
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

// Kruskal算法求解最小生成树
void kruskal() {
    int ans = 0; // 最小权值和
    for (int i = 1; i <= n; i++) {
        parent[i] = i; // 初始化并查集
    }
    sort(edges, edges + m); // 按照边权从小到大排序
    for (int i = 0; i < m; i++) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        int pu = find(u), pv = find(v);
        if (pu != pv) { // 不形成环路
            parent[pu] = pv; // 更新并查集
            ans += w; // 加入该边
            adj[u].push_back({v, w}); // 存储该边
            adj[v].push_back({u, w});
        }
    }
    cout << "最小权值和为：" << ans << endl;
    for (int i = 1; i <= n; i++) {
        cout << i << ": ";
        for (int j = 0; j < adj[i].size(); j++) {
            cout << "(" << adj[i][j].v << ", " << adj[i][j].w << ") ";
        }
        cout << endl;
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }
    kruskal();
    return 0;
}

以上就是Kruskal算法的邻接矩阵和邻接表实现。