本文共 3615 字，大约阅读时间需要 12 分钟。

最小生成树算法（Kruskal和Prim）

最小生成树（Minimum Spanning Tree, MST）是图中连接所有顶点并不包含环路的最低权重的树。生成树需要满足以下两个条件：

最小生成树的构造方法主要有Kruskal算法和Prim算法两种，以下将分别介绍这两种算法的实现过程和注意事项。

1. Kruskal算法

Kruskal算法的主要思想是通过不断添加不形成回路的边，来构造最小生成树。该算法的具体步骤如下：

1. 初始化

• 定义一个并查集结构（Union-Find），用于跟踪各个顶点的连通性。
• 将所有的边按权值从小到大排序，以便按顺序选择边。

2. 遍历边

• 从最小权值的边开始遍历。
• 对于每一条边，检查其两个顶点是否已经连通。
• 如果两个顶点不连通，将它们合并到同一个连通分量中，并将该边加入到最小生成树中。
• 如果两个顶点已经连通，则跳过这条边（因为会形成回路）。

3. 处理特殊情况

• 当遍历完所有边后，如果边的数量比顶点数少至少一，就表明已经构造出了最小生成树。
• 否则，表明图中存在环路，或者边的数量不足以连接所有顶点。

并查集（Union-Find）的作用

• 用于快速判断两个顶点是否连通。
• 提供路径压缩和按秩合并两个树，从而保证合并操作的高效性。

Kruskal算法的优点

• 简单易懂，且每次操作时间复杂度较低（基于边的排序）。
• 适合处理大量边的稀疏图。

实现代码示例

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;struct edge {    int u, v, w;};// 并查集初始化bool findParent(int x, int parent[]) {    if (parent[x] != x) {        parent[x] = findParent(parent[x], parent);    }    return parent[x];}void kruskal(vector
        
          parent, vector
         
          & res, vector
          
           
            > adj) { sort(adj.begin(), adj.end(), [](const edge& a, const edge& b) { return a.w < b.w; }); res.resize(adj.size() + 1); for (int i = 1; i <= adj.size(); ++i) res[i] = -1; for (int i = 1; i <= adj.size(); ++i) { int u = adj[i].u, v = adj[i].v; int pu = findParent(u, parent), pv = findParent(v, parent); if (pu != pv) { // 合并两个不同的连通分量 if (res[pu] == -1 && res[pv] == -1) { res[pu] = adj[i].w; res[pv] = adj[i].w; } else if (res[pu] == -1) { res[pu] = adj[i].w; } else { res[pv] = max(res[pv], res[pu] + adj[i].w); } parent[pu] = pv; ++cnt; } } // 计算最小生成树的权重总和 int sum = 0; for (int i = 1; i <= n; ++i) { if (res[i] != -1) { sum += res[i]; } } return sum;}int main() { // 输入处理 // ... cout << (sum <= c ? "Yes" : "No") << endl; return 0;}
           
          
         
        
       
      
     
    
   

2. Prim算法

Prim算法的思路是从一个起始点出发，逐步扩展最小生成树的集合。具体步骤如下：

1. 初始化

• 建立一个距离数组dist[]，记录每个顶点到已加的最小生成树的距离初始值均为较大的数（如INF）。
• 创建一个访问标记数组vis[]，用于记录已经加入的顶点。
• 选择一个起始点（如顶点0），并初始化该点的距离和访问标记。

2. 引入边

• 在最小生成树中，每次选择一个未被访问的顶点，找到该顶点到最小生成树十近的点，并将该边加入生成树。

3. 更新距离

• 当加入新顶点u后，更新所有未访问的顶点到u的最小距离。

过程描述

• 初始时，vis[]中只有起始点被标记，距离数组中只有起始点距离为0。
• 在循环体中：
• 找到距离起始点最远的未被访问的顶点t。
• 将边t连接到最近的已访问点v。
• 如果t已经纳入生成树，更新生成树的总权重。
• 标记t为已访问，并更新所有顶点到t的最短距离。

注意事项

• 起始点的选择对算法性能影响较大。若多次运行Prim算法，较复杂的数据结构选择可以优化性能。
• 需要区分是否允许边有向或无向。若有向，则需要去除方向重复的边。

Prim算法的优点

• 每次选择最短边，直到生成树构造完成。
• 适合处理稠密图，展开速度可能高于Kruskal算法。

实现代码示例

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;int main() {    // 初始化输入结构    const int INF = 1e9;    vector
       
        
         > adj; // 无向图的边列表 int n, m, c; // 输入顶点数、边数、目标权重 // 输入边数据并构建邻接矩阵 while (cin >> c >> n >> m) { memset(adj, INF, sizeof(adj)); for (int i = 0; i < m; ++i) { int u, v, w; cin >> u >> v >> w; adj[u-1][v-1] = min(w, adj[u-1][v-1]); adj[v-1][u-1] = min(w, adj[v-1][u-1]); } } vector
         
           dist(n, INF), vis(n, 0), res; // 起始点设为0 vis[0] = 1; dist[0] = 0; res = 0; for (int i = 0; i < n; ++i) { if (i == 0) res = dist[i]: else if (vis[i]) continue; int t = -1; for (int j = 0; j < n; ++j) { if (!vis[j] && (t == -1 || dist[t] > dist[j])) { t = j; } } if (t == -1) break; if (i == 0) { res += dist[t]; vis[t] = 1; for (int j = 0; j < n; ++j) { dist[j] = min(dist[j], dist[t] + adj[t][j]); } } else { res += min(res, dist[t] + (i - 1 ? min(dist[u], dist[v]) : 0)); // 类似逻辑需要根据具体实现细化 } vis[t] = 1; for (int j = 0; j < n; ++j) { dist[j] = min(dist[j], dist[t] + adj[t][j]); } } if (res > c) { cout << "No" << endl; } else { cout << "Yes" << endl; } return 0;}
         
        
       
      
     
    
   

总结

• Kruskal算法强调边的排序和并查集的操作，适合稀疏图。
• Prim算法基于最短路径选择边，适合稠密图。
• 具体选择哪种算法需要根据实际问题中图的密集程度来决定。同时，合理配置初始化参数和优化细节能够显著影响算法性能。

转载地址：http://ivphz.baihongyu.com/