prim算法中，closedge[j].lowcost 是干什么用的。新定点并入U后重新选择最小边。那段代码没看懂。 辅助

Question

prim算法中，closedge[j].lowcost 是干什么用的。新定点并入U后重新选择最小边。那段代码没看懂。 辅助数组初始化，没看懂。是不是把那一列都初始化了。

我看的教材是严蔚敏的数据结构。
求解。我就还10分了。不好意思。

Answer 1

在看严蔚敏的这个prim算法之前，我是看的《算法导论》上的prim算法，感觉那个更容易理解prim算法，只是严的有相应的步骤，可以照着实现，网上好多实现prim算法的，貌似也是基于这个。那个closedge[j].lowcost是用来记录V到U-V的权值的（V是已经选择的边，U是所有的边，U-V是剩下的边），在这里可以找到V到U-V的最小权值。你手边应该有书吧，那我就对着严的书说了，对于V1有V2，V3，V4分别是6，1，5，这时可以存入数组（对着那个P174的表），然后选了V3，这个时候就是需要更新closedge.lowcost，因为V2到V1是6而V2到V3是5，所以P175那边的算法倒数第六行的for循环就是用来更新这个的，因为对于新加入的点，可能会出现上面说的情况，其余应该没什么问题的吧