数据结构考研分类复习真题 第七章 图[35]

．考虑右图

()从顶点A出发求它的深度优先生成树

()从顶点E出发求它的广度优先生成树

()根据普利姆(Prim) 算法

求它的最小生成树【上海交通大学 六 (分)】

在什么情况下Prim算法与Kruskual算法生成不同的MST？【西安电子科技大学 计应用 一 (分)】

．下面是求无向连通图最小生成树的一种方法

将图中所有边按权重从大到小排序为(ee…em)

i:=

WHILE (所剩边数 >=顶点数)

BEGIN

从图中删去ei

若图不再连通则恢复ei

i:=i+

END

试证明这个算法所得的图是原图的最小代价生成树【北京邮电大学 五 (分)】

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []