最小生成树是否唯一求解答
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/24 03:36:10
最小生成树是否唯一求解答
最小生成树是否唯一求解答
最小生成树是否唯一求解答
摘要：最小生成树是图论的经典问题,求最小生成树以及求最小生成树的权值和得到了足够关注,而很少人去研究.对于给定的图而言,因为最小生成树的权值和是确定的,所以最小生成树不唯一当且仅当最小生成树的形状不唯一.本文提出判断的三种方法并且对它们给予分析和评价.关键词：最小生成树；唯一；prim算法；kruskal算法；次小生成树中图分类号：TP301.6 文献标识码：A文章编号：1007-9599 (2011)06-0000-02Minimum Spanning Tree If the Unique Wu Yuliang,Kong Fanlong(Central China Normal University,Wuhan430079,China)Abstract:Minimum spanning tree is a classic problem of graph theory,find the minimum spanning tree minimum spanning tree,and find the weight and get enough attention,and few people to study the minimum spanning tree is unique.For a given graph is concerned,because the weights and the minimum spanning tree is determined,so the minimum spanning tree is not unique and only if the shape of the minimum spanning tree is not unique.Determine whether the proposed minimum spanning tree,and the only three ways to give their analysis and evaluation.Keywords:Minimum spanning tree;Unique;Prim algorithm;Kruskal algorithm;Small spanning tree一、三种方法判断最小生成树(MST)是否唯一（一）借助prim算法提出的方法prim算法的基本思想是：首先选取图中的任意一个顶点v作为树的根加入生成树的集合Q中,之后不断往生成树中(集合Q中)添加顶点w,顶点w满足与集合Q中的某个顶点之间有边,且该边上的权值是此时所有连接集合Q中的结点与不在集合Q中的结点的边中权值最小的,如此加入n-1个结点后,就形成了ＭＳＴ.（剩余3202字）