本文围绕 C++实现最小生成树Prim算法：从图论基础到邻接矩阵实现的完整代码讲解展开。通过系统化的理论与实战结合，读者可以在理解基本概念的基础上掌握基于邻接矩阵的 Prim 实现要点与完整代码。
1. 图论基础：最小生成树与 Prim 的关系
1.1 最小生成树的定义
在图论中，最小生成树（MST）是一个使得所有顶点连接且边权之和最小的生成树。对于一个连通无向图，MST 的存在性与唯一性取决于边权的情况，通常情况下可能不唯一，但总权重是最小的。
Prim算法是一种贪心算法，用来逐步构建 MST。它从一个起始顶点开始，在当前顶点集合外部边中选取权值最小的边，把对应顶点加入集合，重复直到覆盖所有顶点。
在与邻接矩阵结合时，边权用一个二维矩阵表示，矩阵中无边用一个极大值（如 INF）表示。这样可以快速判断是否存在边以及边的权值。
1.2 何谓 Prim 的贪心策略
Prim 的核心思想是“局部最优解 → 全局最优解”，通过在每一步选择带权最小的边来扩展已知的最小生成树的边集。
在实现中，最重要的三个结构是“key 数组”、“parent 数组”和“inMST 标记”。 key[v] 表示从已有 MST 的顶点集连接到 v 的最小边权，parent[v] 给出边的上一顶点。
初始时，所有 key 为无穷大，只有起始点的 key 为 0，这样它就会被选中进入 MST。随着循环进行，对每个未在 MST 的顶点，更新 key 和 parent，直至所有顶点被包含。
2. Prim 算法核心思想
2.1 贪心策略与关键变量
在实现中，最重要的三个结构是“key 数组”、“parent 数组”和“inMST 标记”。 key[v] 表示从已有 MST 的顶点集连接到 v 的最小边权，parent[v] 给出边的上一顶点。
初始时，所有 key 为无穷大，只有起始点的 key 为 0，这样它就会被选中进入 MST。随着循环进行，对每个未在 MST 的顶点，更新 key 和 parent，直至所有顶点被包含。
2.2 邻接矩阵下的边界检查
采用邻接矩阵表示时，遍历邻接行时可以快速判断某条边是否存在以及权值大小。若边不存在，权值用 INF 表示，以避免被误选。
3. 邻接矩阵与实现细节
3.1 邻接矩阵的概念
邻接矩阵是一种直观的图表示：矩阵的行列对应顶点，元素值表示边的权值，对称且对无边设置一个大数值。
3.2 在 Prim 中的应用
在 Prim 的实现里，选取最小 key 值的未在 MST 的顶点，将其加入 MST，然后用该顶点更新邻接顶点的 key 与 parent。为了保证效率，通常需要一个选择最小 key 的线性扫描，时间复杂度为 O(V^2)。
4. C++ 实现：完整代码讲解
4.1 设计思路与数据结构
为实现的清晰与可移植性，本文给出一个基于邻接矩阵的实现框架。核心数据结构包括：邻接矩阵、key、parent、inMST。
4.2 完整代码
下面给出一个完整的 C++ 实现，可以直接在支持 C++ 的编译环境中运行。请注意，示例中使用了一个简单的示例图来演示 Prim 的工作过程。
#include <bits/stdc++.h>
using namespace std;
class PrimAdjMatrix {
public:int V;vector<vector<int>> adj;const int INF = 1000000000;PrimAdjMatrix(int n): V(n), adj(n, vector<int>(n, INF)) {}void addEdge(int u, int v, int w) {adj[u][v] = adj[v][u] = w;}vector<int> primMST() {vector<int> key(V, INF), parent(V, -1);vector<bool> inMST(V, false);key[0] = 0;for (int count = 0; count < V - 1; ++count) {int u = -1;int minKey = INF;for (int i = 0; i < V; ++i) {if (!inMST[i] && key[i] < minKey) {minKey = key[i];u = i;}}if (u == -1) break; // 不连通图的处理inMST[u] = true;for (int v = 0; v < V; ++v) {int w = adj[u][v];if (w != INF && !inMST[v] && w < key[v]) {key[v] = w;parent[v] = u;}}}return parent;}int totalWeight(const vector<int>& parent) {int sum = 0;for (int v = 0; v < V; ++v) {int u = parent[v];if (u != -1) sum += adj[v][u];}return sum;}void printEdgeList(const vector<int>& parent) {for (int v = 0; v < V; ++v) {int u = parent[v];if (u != -1) {cout << u << \" - \" << v << \" (\" << adj[u][v] << \")\" << endl;}}}
};int main() {// 示例图：6个顶点PrimAdjMatrix g(6);// 添加边（无向图）g.addEdge(0,1,4);g.addEdge(0,2,4);g.addEdge(1,2,2);g.addEdge(1,3,5);g.addEdge(2,3,5);g.addEdge(2,4,11);g.addEdge(3,4,2);g.addEdge(3,5,9);g.addEdge(4,5,1);auto parent = g.primMST();int total = g.totalWeight(parent);cout << \"Total MST weight: \" << total << endl;g.printEdgeList(parent);return 0;
}运行结果解析：输出显示了 MST 的总权重以及构成 MST 的边，帮助你直观理解 Prim 算法在邻接矩阵上的实际效果。
5. 运行示例与结果分析
5.1 输入示例与准备
在实际工程中，图的加载可以来自文件或网络数据，最关键的是确保 邻接矩阵的对称性与 INF 表示无边。下面的示例仍然展示了一个简单的连通图。
此外，起始顶点的选择对 MST 的边的具体形式并无影响（只要图是连通的），但总权重恒等于 MST 的最优值。
5.2 输出解读
输出的每一对边都表示 MST 的一条边，边权之和等于总权重，该值在 totalWeight 函数中计算。
关于复杂度，在纯粹的邻接矩阵实现中，时间复杂度为 O(V^2)，因为需要在 V 次循环中线性扫描未在 MST 中的顶点。若改用优先队列实现，理论上可以将复杂度降至 O(E log V)（适用于稀疏图）。
