我认为判断prim算法唯一性有两个方面:
1.假设目前已经生成的集合为P,现在需要把集合P外的距P最近的点a加到集合P中。在这个过程中,如果a与集合P中的b、c都构成了最短距离,则此时把a加入到P中有两种方式即:与b相连和与c相连,这就完完全全成为了两棵不同的最小生成树。
2.假设目前已经生成的集合为P,现在需要把集合P外的距P最近的点a加到集合P中。在这个过程中,如果a、b分别与集合P中的x、y都构成了最短距离,则此时同样有两种方式即:加入a和加入b。但是,这两种方式不一定形成不同的树。
为此,我们需要加入另外的条件,当a、b分别与P中的x、y构成最短距离,不妨先把a加入其中形成P',如果此时b到P'中y的距离和b到P中y的距离相等且还是最短距离,则还是同一棵树。否则,构成了两棵不同的最小生成树。