若将森林中的每棵树视作一个等价类，则Kruskal算法迭代过程所涉及的计算不外乎两类：
支持以上操作接口的数据结构，即所谓的独立集(disjoint set)，亦称作并查集(union-find set)。
a)试基于此前介绍过的基本数据结构实现并查集，并用以组织Kruskal算法中的森林;
b)按你的实现，find()和union()接口的复杂度各是多少？相应地，Kruskal算法的复杂度呢？
如搜索结果不匹配，请 联系老师 获取答案
更多“若将森林中的每棵树视作一个等价类，则Kruskal算法迭代过…”相关的问题
第1题
Joseph Kruskal于1956年提出了构造极小支撑树的另一算法：
将每个顶点视作一棵树，并将所有边按权重非降排序;
依次考查各边，只要其端点分属不同的树，则引入该边，并将端点所分别归属的树合二为一;
如此迭代，直至累计已引入n-1条边时，即得到一棵极小支撑树。
试证明：
a)算法过程中所引入的每一条边，都是某一割的极短跨越边(因此亦必属于某棵极小支撑树);
b)算法过程中的任一时刻，由已引入的边所构成的森林，必是某棵极小支撑树的子图;
第2题
若一个具有n个节点、k条边的非连通无向图是一个森林(n＞k)，则该森林中必有(19)棵树。
A．k
B．n
C．n-k
D．n+k
第3题
若一个具有n个结点、k条边的非连通无向图是一个森林(n＞k)，则该森林中必有(34)棵树。
A．k
B．n
C．n-k
D．n+k
第4题
若一个具有n个结点、k条边的非连通无向图是一个森林(n，k)，则该森林中必有(58)棵树。
A．k
B．n
C．n-k
D．n+k
第7题
程分为若于阶段，每一阶段选取若干条边.算法思路如下：
(1)将每个顶点视为一棵树，图中所有顶点形成一个森林;
(2)为每棵树选取一条边，它是该树与其他树相连的所有边中权值最小的一条边，把该边加入生成树中。如果某棵树选取的边已经被其他树选过，则该边不再选取。
重复以上操作，直到整个森林变成一棵树。
以图8-44所示的图为例，写出执行以上算法的过程。
第8题
已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小生成树(假设以①为起点，试画出构造过程)。
【哈尔滨工业大学2000九(8分)】
第9题
用Prim算法和Kruskal算法构造图的最小生成树，所得到的最小生成树（）。
A．相同
B．不相同
C．可能相同，可能不同
为了保护您的账号安全，请在“赏学吧”公众号进行验证，点击“官网服务”-“账号验证”后输入验证码“”完成验证，验证成功后方可继续查看答案！
微信搜一搜
赏学吧
微信搜一搜
赏学吧
