G=(V,E)是一个带有权的连通图,如图所示。 G如图所示,请找出G的所有最小生成树。

admin2019-08-15  25

问题 G=(V,E)是一个带有权的连通图,如图所示。
G如图所示,请找出G的所有最小生成树。

选项

答案最小生成树有两棵。下面给出顶点集合和边集合,编以三元组(Vi,Vj,W)形式,其中W代表权值。 V(G)={1,2,3,4,5} E1(G)={(4,5,2),(2,5,4),(2,3,5),(1,2,7)}; E2(G)={(4,5,2),(2,4,4),(2,3,5),(1,2,7)} 提示:此题考查的知识点是最小生成树的定义。该题说明图的最小生成树不唯一,但权值和唯一,出现两个或两个以上的情况是因为有权值相同的边。牢记Prim(选图的顶点)、Kruskal(选图的边,边上权值排序)两种算法的区别及算法步骤。

解析
转载请注明原文地址:https://jikaoti.com/ti/usGjFFFM
0

相关试题推荐
随机试题
最新回复(0)