题目内容
(请给出正确答案)
[主观题]
若无向图中所有边的权重均相等,试基于广度优先搜索的框架设计并实现一个算法,在o(n+e)时间内计算出某一起始顶点到其余顶点的(最小)距离和一条(最短)通路。
查看答案
如果结果不匹配,请 联系老师 获取答案
A、顶点
B、边
C、权
D、权值
Joseph Kruskal于1956年提出了构造极小支撑树的另一算法:
将每个顶点视作一棵树,并将所有边按权重非降排序;
依次考查各边,只要其端点分属不同的树,则引入该边,并将端点所分别归属的树合二为一;
如此迭代,直至累计已引入n-1条边时,即得到一棵极小支撑树。
试证明:
a)算法过程中所引入的每一条边,都是某一割的极短跨越边(因此亦必属于某棵极小支撑树);
b)算法过程中的任一时刻,由已引入的边所构成的森林,必是某棵极小支撑树的子图;
对于如图8-5所示的有向图,试写出:
(1)从顶点①出发进行深度优先搜索所得到的深度优先生成树;
(2)从顶点②出发进行广度优先搜索所得到的广度优先生成树。