Prim围绕顶点归属状态维护in_mst[]、dist[]和parent[]，实现局部扩张；Kruskal依赖排序边数组与并查集，专注全局边选择与连通性判别。
Prim和Kruskal在变量设计上本质不同：Prim围绕“顶点归属状态”动态维护距离数组与集合标记，Kruskal则聚焦“边的全局排序”与“连通性判别”，变量用途直接反映算法逻辑重心。
Prim算法的核心变量：状态驱动的局部扩张
Prim维护一组与当前生成树直接关联的状态变量，所有操作都服务于“如何把下一个最近的外部顶点拉进来”这一目标。
- in_mst[]：布尔数组，标记每个顶点是否已加入MST。这是判断“内外边界”的唯一依据，不可省略或用其他逻辑替代。
- dist[]：整型数组，记录每个未入树顶点到当前MST的最短边权值（不是到起点的距离）。每次新顶点加入后必须遍历其邻边更新该数组。
- parent[]：用于回溯构造边集，保存每个顶点是被哪条边“拉进”MST的。若只需总权值可省略，但输出具体边时必须保留。
Kruskal算法的核心变量：静态结构+动态判别
Kruskal不维护顶点状态，而是预处理边、再逐条验证，变量设计更偏数据组织与判定效率。
-
边数组（如vector
） ：必须显式存储所有边，并按权值升序排序。这是算法起点，无法绕过；排序后原图结构信息即被固化。 - 并查集（UnionFind）：含parent[]和rank[]（或仅path-compressed parent），专用于O(α(n))时间判断加边是否成环。它不关心顶点“属于谁”，只回答“u和v是否已连通”。
- 边计数器：统计已选边数，达到n−1立即终止。不需要dist或in_mst这类连续状态变量。
变量生命周期与内存特征差异
两者在实际编码中对内存和初始化的要求明显不同，直接影响大规模图的可行性。
- Prim朴素版依赖邻接矩阵，空间固定为O(n²)，即使图很稀疏也要开满二维数组；而Kruskal只存边，空间为O(E)，天然适配稀疏场景。
- Prim的dist[]和in_mst[]需全程在线更新，每次迭代都要扫描全部顶点；Kruskal的边数组排序只需一次，后续仅顺序访问，缓存友好性更好。
- 当图以邻接表输入时，Prim若改用堆优化，变量会新增优先队列（如priority_queue
>），此时dist[]退居辅助角色，而Kruskal变量结构基本不变。
调试与常见错误点
变量误用是初学者超时或错解的主因，关键区别在于“谁定义了当前有效范围”。
- Prim中误把dist[v]当成到起点距离——它始终是到当前MST集合的最小边权，不是单源最短路径。
- Kruskal中未对边排序就直接遍历，或并查集未做路径压缩，会导致复杂度退化甚至逻辑错误。
- 混用顶点编号习惯：Prim常从0开始索引，Kruskal边结构体里u/v若从1开始，而并查集初始化没对应调整，极易越界或漏判。
