在一个有n个顶点的带权连通图中,有条边,则应该选用()算法来求这个图的最小生成树,从而使计算时间较少,
A、Prim
B、Kruskal
图8-8是一个连通图,请画出:
(1)以顶点①为根的DFS树,
(2)如果有关节点,请找出所有的关节点。
(3)如果想把该连通图变成重连通图,至少在图中加几条边?如何加?
点是否在同一个连通分量上,在该算法中选择权值最小的边的原则是该边不能在图中构成(②),它主要适用于(③)。
A、稀疏
B、稠密
C、完全
D、不完全
为,这里的路径长度是指路径中所含的边数。编写一个算法求T的直径、并分析算法的时间复杂度。
A、K
B、N
C、N-K
D、l
a)若套用Kruskal或Prim算法构造EMST(G),各需多少时间?
b)试设计一个算法,在o(nlogn)时间内构造出EMST(G);
c)试证明你的算法已是最优的(亦即,在坏情况下,任何此类算法都需要o(nlogn)时间)。