关于Prim算法维基百科伪代码步骤3.b的正确性疑问

你看到的Prim算法伪代码中，步骤3.b写的是「Add v to F」，这里的关键在于伪代码对F（森林）的定义：它不是单纯的边集合，而是用来追踪「已经被纳入生成树/森林的顶点构成的子图结构」。

具体解释下：

• 初始状态下F是空森林，也就是没有任何顶点和边的空结构。
• 第一次执行步骤3.a时，会选出C[v]最小的顶点（针对非连通图的森林版本，初始所有C[v]设为无穷，第一次选中的顶点没有对应的有效E[v]——因为E[v]初始是无连接的特殊标记），这时候只能把该顶点加入F，作为森林里的第一个孤立节点。
• 后续选中的每个v，都带有对应的E[v]（也就是连接到已在F中顶点的最小权重边），但伪代码里的F核心作用是记录「已处理完成的顶点集合」，最终要得到最小生成树的边集合，需要遍历所有顶点的E[v]，排除初始的特殊标记项即可。

你提出的「将步骤3.b改为Add E[v] to F」的思路，其实更贴合我们对「最小生成树是边集合」的常规认知。但原伪代码的设计逻辑是用F追踪顶点范围，而非直接构建边集合，所以步骤3.b的写法是符合它自身定义的。如果要让伪代码直接生成边集合，你的修改是合理的，但需要同步调整F的初始定义（改为空边集合）以及第一次选顶点时的逻辑（不添加边）。

内容的提问来源于stack exchange，提问作者MikeTheTall