若将森林中的每棵树视作一个等价类,则Kruskal算法迭代过程所涉及的计算不外乎两类:支持以上操
若将森林中的每棵树视作一个等价类,则Kruskal算法迭代过程所涉及的计算不外乎两类:
支持以上操作接口的数据结构,即所谓的独立集(disjoint set),亦称作并查集(union-find set)。
a)试基于此前介绍过的基本数据结构实现并查集,并用以组织Kruskal算法中的森林;
b)按你的实现,find()和union()接口的复杂度各是多少?相应地,Kruskal算法的复杂度呢?
若将森林中的每棵树视作一个等价类,则Kruskal算法迭代过程所涉及的计算不外乎两类:
支持以上操作接口的数据结构,即所谓的独立集(disjoint set),亦称作并查集(union-find set)。
a)试基于此前介绍过的基本数据结构实现并查集,并用以组织Kruskal算法中的森林;
b)按你的实现,find()和union()接口的复杂度各是多少?相应地,Kruskal算法的复杂度呢?
当元素类型为字符串时,为避免复杂的散列码转换,可以改用键树(trie)结构来实现词典ADT。
a)remove()接口复杂度中的因子r可否消除?
b)put()接口复杂度中的因子r可否消除?
c)试举例说明,以上实现方式在最坏情况下可能需要多达Ω(nr)的空间,其中n=|S|为字符串集的规模。
d)试改用列表来实现各节点,使所需空间的总量线性正比于S中所有字符串的长度总和——当然,get()接口的效率因此会降至O(hr),其中h为树高,同时也是Ss中字符串的最大长度。
e)键树中往往包含大量的单分支节点。试如图x9.5所示,通过折叠合并相邻的单分支节点,进一步提高键树的时、空效率。改进之后,键树的时、空复杂度各是多少?
f)习题[8-19](173页)曾介绍过四叉树(quadtree)结构,并指出其深度不受限制的缺陷。若将四个象限的二进制编码视作字符,即将字符表取作∑={00,01,10,11},则四叉树可以看作键树的特例,试基于这一理解,仿照以上技巧对四叉树进行压缩,使其深度不致超过O(n)。
Joseph Kruskal于1956年提出了构造极小支撑树的另一算法:
将每个顶点视作一棵树,并将所有边按权重非降排序;
依次考查各边,只要其端点分属不同的树,则引入该边,并将端点所分别归属的树合二为一;
如此迭代,直至累计已引入n-1条边时,即得到一棵极小支撑树。
试证明:
a)算法过程中所引入的每一条边,都是某一割的极短跨越边(因此亦必属于某棵极小支撑树);
b)算法过程中的任一时刻,由已引入的边所构成的森林,必是某棵极小支撑树的子图;
A.在Contoso森林中配置客户端计算机使用TailspinToysDNS服务器作为备用DNS服务器
B.在ActiveDirectory中创建一个新的条件转发和存储。复制新的条件转发到Contoso林中的所有DNS服务器
C.在Contoso林中创建一个新的应用程序目录分区。让所有DNS服务器支持目录分区
D.在Contoso林的一台DNS服务器上创建新的全局名称主机(A)记录。配置主机(A)使用TailspinToys域名和TailspinToys林的DNS服务器的IP地址记录