欢迎来到雄杰鑫电商资讯网
技术教程

C++如何实现一个最小生成树算法_C++图论之Prim与Kruskal算法详解

下次还敢 次阅读
Prim算法从点出发，每次选最近顶点加入生成树，适合稠密图；Kruskal按边权排序贪心选取，用并查集判环，适合稀疏图；两者时间复杂度分别为O(V²)和O(E log E)，应根据图的密度选择。

在图论中，最小生成树（Minimum Spanning Tree, MST）是连接无向连通图中所有顶点的一棵树，且边的权值总和最小。C++中常用的两种求解MST的算法是Prim算法和Kruskal算法。下面详细介绍它们的原理与实现方式。

Prim算法：从点出发构建最小生成树

Prim算法的核心思想是从一个起始顶点开始，逐步扩展生成树，每次选择与当前生成树相连且权值最小的边所连接的新顶点，直到覆盖所有顶点。

适用场景：稠密图（边数接近顶点数平方），使用邻接矩阵存储更高效。

Prim算法步骤：

  • 初始化一个布尔数组visited标记顶点是否已加入生成树，距离数组dist记录各顶点到生成树的最短距离
  • 从任意起点（如0号顶点）开始，更新其邻接点的距离
  • 每次从未访问顶点中选出dist最小的顶点u，将其加入生成树
  • 用u更新其所有邻接点的距离
  • 重复上述过程直到所有顶点都被访问

代码实现（邻接矩阵）：

#include 
#include 
#include 
using namespace std;

const int INF = INT_MAX;
int prim(vector>& graph, int n) {
vector dist(n, INF);
vector visited(n, false);
dist[0] = 0;
int totalWeight = 0;
for (int i = 0; i zuojiankuohaophpcn n; i++) {
    int u = -1;
    for (int j = 0; j zuojiankuohaophpcn n; j++) {
        if (!visited[j] && (u == -1 || dist[j] zuojiankuohaophpcn dist[u]))
            u = j;
    }

    if (dist[u] == INF) return -1; // 图不连通
    visited[u] = true;
    totalWeight += dist[u];

    for (int v = 0; v zuojiankuohaophpcn n; v++) {
        if (graph[u][v] != 0 && !visited[v] && graph[u][v] zuojiankuohaophpcn dist[v]) {
            dist[v] = graph[u][v];
        }
    }
}
return totalWeight;
}


Kruskal算法：按边排序贪心选取


Kruskal算法基于贪心策略，将所有边按权值从小到大排序，依次尝试加入生成树，若加入后不形成环，则保留该边，否则跳过。


适用场景：稀疏图（边较少），使用边列表存储效率更高。


Kruskal算法关键点：


    

  • 需要对边进行排序
    • 

  • 使用并查集（Union-Find）判断是否形成环
    • 

  • 当加入n-1条边时，生成树完成
    • 



代码实现：
#include 
#include 
#include 
using namespace std;

struct Edge {
int u, v, weight;
bool operator<(const Edge& other) const {
return weight < other.weight;
}
};
class UnionFind {
vector parent;
public:
UnionFind(int n) {
parent.resize(n);
for (int i = 0; i < n; i++) parent[i] = i;
}
int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);
    return parent[x];
}

void unite(int x, int y) {
    parent[find(x)] = find(y);
}

bool connected(int x, int y) {
    return find(x) == find(y);
}
};


int kruskal(vector& edges, int n) {
sort(edges.begin(), edges.end());
UnionFind uf(n);
int totalWeight = 0;
int edgesAdded = 0;
for (const Edge& e : edges) {
    if (!uf.connected(e.u, e.v)) {
        uf.unite(e.u, e.v);
        totalWeight += e.weight;
        edgesAdded++;
        if (edgesAdded == n - 1) break;
    }
}
return edgesAdded == n - 1 ? totalWeight : -1; // 不连通返回-1
}


两种算法对比与选择建议


理解两者差异有助于在实际问题中做出合适选择。


时间复杂度比较：


    

  • 
Prim（邻接矩阵）：O(V²)，适合顶点少、边多的情况
    • 

  • 
Prim（优先队列优化）：O(E log V)，适用于稀疏图
    • 

  • 
Kruskal：O(E log E)，主要开销在排序，适合边较少的图
    • 



空间复杂度：


    

  • Prim通常使用邻接矩阵或邻接表，空间O(V²)或O(E)
    • 

  • Kruskal只需存储边列表，空间O(E)
    • 



选择建议：


    

  • 图很稠密（比如完全图）→ 优先考虑Prim
    • 

  • 图较稀疏或边已以列表形式给出 → Kruskal更直观高效
    • 

  • 需要频繁添加/删除边 → Kruskal更容易维护
    • 



基本上就这些。两种算法都能正确求出最小生成树，关键是根据数据规模和结构选择合适的方法。实际编程中注意处理图不连通的情况，避免无限循环或错误结果。






            
 算法 更高 都能 适用于 只需 是从 两种 将其 go stream ios edge 较少 循环 c++ 布尔 int sort union 求出

相关文章

按ESC键退出。