求最小生成树的Kruskal算法在边较少,顶点较多时效率较高。() - 快问云问答

第1题

计算连通网的最小生成树的Dijkstra算法可简述如下：将连通网所有的边以方便的次序逐条加人到初

始为空的生成树的边集合S中。每次选择并加人一条边时，需要判断它是否会与先前加人S中的边构成回路。如果构成了回路，则从这个回路中将权值(花费)最大的边退选。试设计一个求最小生成树的算法。要求以邻接矩阵作为连通网的存储结构，并允许在运算后改变邻接矩阵的结构。

点击查看答案

第2题

关于解决最小代价生成树问题的Prim算法的下述说法，不正确的是（)。

A.优先队列Q中顶点的键值指这个顶点与A集合中点的最小权边的权重

B.从Q中取出一个顶点的实质是在应用MST性质选择连接A与VA的最小权边

C.算法执行结束后，生成树有n-1个顶点

D.算法以优先队列为空为结束条件

点击查看答案

第3题

B.Kruskal算法：（贪心) 按权值递增顺序删去图中的边，若不形成回路则将此边加入最小生成树。funct

B.Kruskal算法：(贪心)

按权值递增顺序删去图中的边，若不形成回路则将此边加入最小生成树。

function find(v:integer):integer; {返回顶点v所在的集合}

var i:integer;

点击查看答案

第4题

Joseph Kruskal于1956年提出了构造极小支撑树的另一算法：将每个顶点视作一棵树，并将所有边按权

Joseph Kruskal于1956年提出了构造极小支撑树的另一算法：

将每个顶点视作一棵树，并将所有边按权重非降排序;

依次考查各边，只要其端点分属不同的树，则引入该边，并将端点所分别归属的树合二为一;

如此迭代，直至累计已引入n-1条边时，即得到一棵极小支撑树。

试证明：

a)算法过程中所引入的每一条边，都是某一割的极短跨越边(因此亦必属于某棵极小支撑树);

b)算法过程中的任一时刻，由已引入的边所构成的森林，必是某棵极小支撑树的子图;

点击查看答案

第5题

试举例说明，在最坏情况下，Kruskal算法的确可能需要检查Ω（n²)条边，

点击查看答案

第6题

下列哪项算法是深度学习的重要基础：（）。

A.最小生成树算法

B.最大流-最小割算法

C.A*算法

D.SGD反向传播

点击查看答案

第7题

最小生成树 A.Prim算法： procedure prim（v0:integer);varlowcost,closest:array[1..maxn] o

最小生成树

A.Prim算法：

procedure prim(v0:integer);

var

lowcost,closest:array[1..maxn] of integer;

i,j,k,min:integer;

点击查看答案

第8题

若将森林中的每棵树视作一个等价类，则Kruskal算法迭代过程所涉及的计算不外乎两类：支持以上操

若将森林中的每棵树视作一个等价类，则Kruskal算法迭代过程所涉及的计算不外乎两类：

支持以上操作接口的数据结构，即所谓的独立集(disjoint set)，亦称作并查集(union-find set)。

a)试基于此前介绍过的基本数据结构实现并查集，并用以组织Kruskal算法中的森林;

b)按你的实现，find()和union()接口的复杂度各是多少？相应地，Kruskal算法的复杂度呢？

点击查看答案

第9题

连通图上各边权值均不相同，则该图的最小生成树一定是唯一的。（)

点击查看答案

求最小生成树的Kruskal算法在边较少，顶点较多时效率较高。（)