题目内容

用Prim算法和Kruskal算法构造图的最小生成树,所得到的最小生成树( ).

A. 相同
B. 不相同
C. 可能相同,可能不同
D. 无法比较

查看答案

搜索结果不匹配？点我反馈

更多问题

以下叙述中,正确的是( ).

A. 只要无向连通图中没有权值相同的边,则其最小生成树唯一
B. 只委无向图中有权值相同的边,则其最小生成树一定不唯
C. 从n个顶点的连通图中选取n- 1条权值最小的边,即可构成最小生成树
D. 设连通图G含有n个顶点,则含有n个顶点、n- 1条边的子图一定是 G的生成树

已知带权连通无向图G=(V,E),其中V= {v1,v2, v3, v4, v5, v6, v7},E= {(v1, v2)10, (v1, v3)2, (v3,v4)2, (v3, v6)11, (v2 v5)1, (v4, v5)4, (v4, v6)6, (v5, v7)7, (v6,v7)3} (注:顶点偶对括号外的数据表示边上的权值),从源点V1到顶点V7的最短路径上经过的顶点序列是( )。

A. v1,v2,v5,v7
B. v1,v3,v4,v6,v7
C. v1,v3,v4,v5,v7
D. v1,v2,v5,v4,v6,v7

[2016统考真题]若对n个顶点、e条弧的有向图采用邻接表存储,则拓扑排序算法的时间复杂度是( ).

A. O(n)
B. O(n+e)
C. O(n^2)
D. O(ne)

下列关于图的说法中,正确的是( )。 I有向图中顶点V的度等于其邻接矩阵中第V行中1的个数 II无向图的邻接矩阵一定是对称矩阵,有向图的邻接矩阵- -定是非对称矩阵 III. 在图G的最小生成树G,中,某条边的权值可能会超过未选边的权值 IV.若有向无环图的拓扑序列唯一,则可以唯-确定该图

A. I、II和III
B. III和IV
C. III
D. IV