itgle.com

对(),用Prim算法求最小生成树较为合适,而Kruskal算法适于构造()图的最小生成树。A.完全图B.连通图C.稀疏图D.稠密图

题目
对(),用Prim算法求最小生成树较为合适,而Kruskal算法适于构造()图的最小生成树。

A.完全图

B.连通图

C.稀疏图

D.稠密图

相似考题

1.对________,用 Prim算法求最小生成树较为合适。A、非连通图B、连通图C、稀疏图D、稠密图

2.下面()算法适合构造一个稠密图G的最小生成树。A.Prim算法B、Kruskal算法C.Floyd算法D、Dijkstra算法

3.什么样的连通图其最小生成树是唯一的？用Prim和Kruskal算法求最小生成树的时间复杂度各为多少？它们分别更适合于哪类图？

4.对稀疏图,用 Prim算法求最小生成树较为合适。()此题为判断题(对，错)。

参考答案和解析
参考答案：D,C
更多“对(),用Prim算法求最小生成树较为合适,而Kruskal算法适于构造()图的最小生成树。 ”相关问题

  • 第1题：

    下列（）算法适合构造一个稠密图G的最小生成树。

    A．Prim算法

    B．Kruskal算法

    C．Floyd算法

    D．Dijkstra算法


    Prim算法

  • 第2题：

    下面（）适合构造一个稠密图G的最小生成树。

    A．Prim算法

    B．Kruskal算法

    C．Floyd算法

    D．Dijkstra算法


    A

  • 第3题：

    请分别用Prim算法和Kruskal算法构造以下网络的最小生成树，并求出该树的代价。


    (1)用Prim算法构造最小生成树： ①n=8，只有顶点V 0 在最小生成树中。 mst[7]={{0，1，2}，{0，2，3}，{0，3，∞}，{0，4，∞}，{0，5，∞}，{0，6，∞}，{0，7，∞}} 这里的mst[]中每个元素{i，j，w}对应图中权为w的一条边。 ②在mst[0]到mst[6]找出权值最小的边mst[0]，即(V 0 ，V 1 )，将顶点V 1 及边加入到最小生成树中。 ③调整mst[1]到mst[6]，得到 mst[7]={{0，1，2}，{0，2，3}，{1，3，2}，{0，4，∞}，{0，5，∞}，{0，6，∞}，{0，7，∞}} 这里的黑体{0，1，2}表示该元素对应的边已经在最小生成树中。 ④在mst[1]到mst[6]找出权值最小的边mst[2]，即(V 1 ，V 3 )，将顶点V 3 及边加入到最小生成树中。 ⑤调整mst[2]到mst[6]，得到 mst[7]={{0，1，2}，{1，3，2}，{3，2，1)，{3，4，2}，{3，5，4}，{0，6，∞}，{0，7，∞}} 得到的最小生成树如下图所示： (2)用Kruskal算法构造最小生成树 集合E中按权递增顺序排列为：(V 2 ，V 3 )，(V 4 ，V 5 )，(V 5 ，V 7 )，(V 6 ，V 7 )，(V 0 ，V 1 )，(V 1 ，V 3 )，(V 3 ，V 4 )，(V 4 ，V 6 )，(V 5 ，V 6 )，(V 0 ，V 2 )，(V 3 ，V 5 )。 ①初始时，最小生成树为只有7个顶点的非连通图。 ②边(V 2 ，V 3 )的两个顶点分别属于两个连通分量，将边(V 2 ，V 3 )加入到最小生成树中。 ③同理，将边(V 4 ，V 5 )，(V 5 ，V 7 )，(V 6 ，V 7 )，(V 0 ，V 1 )，(V 1 ，V 3 )，(V 3 ，V 4 )加入到最小生成树中。 得到的最小生成树如下图所示：

  • 第4题：

    36、关于最小生成树的求解，下面说法正确的是:

    A．求解最小生成树的常用算法有Prim算法，Kruskal算法

    B．Kruskal算法每次选择一条最小且不会构成回路权边直至构成一个生成树

    C．Prim 算法从一个结点的子图开始构造生成树：选择连接当前子图和子图外结点的最小权边，将相应结点和边加入子图，直至将所有结点加入子图

    D．从算法复杂度的角度看，Kruskal算法适用于稀疏图，Prim算法适用于稠密图


    ABC

  • 第5题：

    7、下面（）算法适合构造一个稠密图G的最小生成树。

    A．Prim算法

    B．Kruskal算法

    C．Floyd算法

    D．Dijkstra算法


    A

相关内容