1. 最小生成树概述
在图中，最小生成树是一棵包含了所有节点的树，并且所有边的权重之和最小。在计算机科学中，最小生成树是一个重要的概念，由于其应用十分广泛，是算法设计中的一个重要研究方向。常见的求解最小生成树的算法有 Prim 算法和 Kruskal 算法。
2. Prim 算法实现
2.1 Prim 算法基础思路
Prim 算法是一种贪心算法，具体思路如下：
任选一个节点作为起始节点，将其加入生成树中
找到与生成树相连的所有边，并找出权重最小的一条边，将边的目标节点加入生成树中
重复执行步骤2，直到所有节点都已加入生成树中
下面我们来看一下具体实现。
2.2 Prim 算法实现细节
我们可以使用邻接矩阵来表示图，定义一个数组 dist 存储当前每个节点到生成树的最短距离。初始时，所有节点到生成树的距离为无穷大，而起始节点到自己的距离为 0：
#define INF 0x3f3f3f3f
int G[MAXN][MAXN]; // 邻接矩阵
int dist[MAXN]; // 到生成树的最短距离
int visited[MAXN]; // 记录节点是否访问过
void prim(int s) { // s 为起始节点
// 初始化
memset(dist, INF, sizeof(dist));
memset(visited, 0, sizeof(visited));
dist[s] = 0;
for (int i = 0; i < n; i++) { // n 为节点数量
int u = -1;
for (int j = 0; j < n; j++) {
if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
u = j;
}
}
visited[u] = 1;
for (int v = 0; v < n; v++) {
if (!visited[v] && G[u][v] != INF && G[u][v] < dist[v]) {
dist[v] = G[u][v];
}
}
}
}
在上面的代码中，第一个 for 循环用于遍历所有的节点。在每次循环中，我们选择一个距离生成树最近的尚未加入的节点，并将它加入生成树中。然后，我们遍历与该节点相邻的所有节点，并更新它们到生成树的距离。
最后，我们得到了生成树的权重之和。如果需要重建生成树，我们可以使用一个 parent 数组记录每个节点加入树时的父节点，然后从叶节点往根节点回溯即可。
3. Kruskal 算法实现
3.1 Kruskal 算法基础思路
Kruskal 算法也是一种贪心算法，具体思路如下：
将每个节点都看作是一个独立的子树
按边权从小到大依次加入边
如果加入该边后两个节点属于不同的子树，则将两个子树合并成一个子树
重复执行步骤2-3，直到所有节点都属于同一个子树，此时的边集即为最小生成树
下面我们来看一下具体实现。
3.2 Kruskal 算法实现细节
我们可以使用边集数组来表示图，定义一个 parent 数组存储每个节点的父节点，初始时，每个节点都指向自己。然后按照边权从小到大依次加入边，并判断加入该边是否会形成环，如果不形成环，则将两个节点合并。
struct edge {
int u, v, w;
} edges[MAXN * MAXN];
int parent[MAXN];
int find(int x) {
if (x != parent[x]) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void kruskal(int n, int m) { // n 为节点数量，m 为边数量
for (int i = 0; i < n; i++) {
parent[i] = i;
}
sort(edges, edges + m, [](edge a, edge b) {
return a.w < b.w;
});
int cnt = 0, res = 0; // 记录已加入树的边数和生成树权重之和
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;
res += w;
cnt++;
if (cnt == n - 1) break;
}
}
}
在上面的代码中，首先我们将每个节点初始化为一个独立的子树。然后，我们将边按边权从小到大排序，并从小到大加入边。每次加入边之前，我们查找当前两个节点所在的子树的根节点是否相同，如果相同，则说明加入该边会形成环，不能加入；如果不同，则说明可以加入该边，并将两个子树合并成一个子树，并将边的权重加入生成树权重之和。
4. 总结
在本文中，我们分别介绍了 Prim 算法和 Kruskal 算法求解最小生成树的基本思路以及实现细节。两种算法都是贪心算法，并且时间复杂度均为 O(m log n)，其中 m 为边数，n 为节点数。在实际应用中，需要根据数据特点和算法优缺点来选择合适的算法。