在“算法设计手册”中找到了这个问题,问题的解决方案是
Sort2()
initialize-tree(t)
While (not EOF)
read(x);
insert(x,t);
y = Minimum(t)
While (y != NULL) do
print(y → item)
y = Successor(y,t)
它被解释为“第二个问题允许我们在构造树之后使用最小操作和后继操作,我们可以从最小元素开始,然后重复查找后续元素,按照排序顺序遍历元素。”
我想我不是在跟踪Sort2()。如果y被初始化为最小节点,那么它不可能没有任何后续节点吗
当图有多个连通分量时,我不知道如何实现Kruskal算法
根据我对Kruskal算法的理解,它多次向集合中添加最小边。然后,当所有的边都被检查时,它会返回一组最充分的边。
但是,如果我的图是断开的呢?说我有:
A - B - C - D
E - F
假设成本( are )=成本(E)= 1,其余的边大于1。
当我运行Kruskal时,我会得到所有的边的成本,但是我想得到每个连接组件的成本,所以我对所有连接的组件做了一个平均最小的成本。