题目中给出一个无向图,需要判断mst是否唯一。
本题用prim算法来做比较简单,具体来说,当一个节点被两个边更新的时候,如果他被选为下一个放入树中的点,那么连接他的边我们就不能确定了,也就是可能有多个最小生成树。上图,当a点确定的时候,b点更新为8,c点更新为12,然后b被加入树中,然后要更新c点,这时c的值12已经被两条边更新了,所以就可能产生多棵树。
题目中给出一个无向图,需要判断mst是否唯一。
本题用prim算法来做比较简单,具体来说,当一个节点被两个边更新的时候,如果他被选为下一个放入树中的点,那么连接他的边我们就不能确定了,也就是可能有多个最小生成树。上图,当a点确定的时候,b点更新为8,c点更新为12,然后b被加入树中,然后要更新c点,这时c的值12已经被两条边更新了,所以就可能产生多棵树。