gpt4 book ai didi

algorithm - 设计一种算法,在线性时间内找到该图的最小生成树

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:59:43 24 4
gpt4 key购买 nike

我正在研究一个问题,在这个问题中,我得到一个有 n 个顶点和 m 条边的无向图 G,这样每条边 e 的权重 w(e) ∈ {1, 2, 3}。任务是设计一种算法,在线性时间 (O(n + m)) 内找到 G 的最小生成树。

到目前为止,这些是我的想法:

  1. 在我目前正在学习的算法图论类(class)中,我们介绍了 Kruskal 和 Prim 的 MST 算法。也许我可以以某种方式修改这些,以获得线性时间。
  2. 边的排序通常需要对数线性 (O(mlog(m))) 时间;然而,由于所有边的权重都是 1、2 或 3,因此桶排序可用于按边数 (O(m)) 对边进行时间线性排序。

我正在使用以下版本的 Kruskal 算法:

Kruskal(G)
for each vertex 𝑣 ∈ 𝑉 do MAKE−SET(𝑣)
sort all edges in non-decreasing order
for edge 𝑢, 𝑣 ∈ 𝐸 (in the non-decreasing order) do
if FIND 𝑢 ≠ FIND(𝑣) then
colour (𝑢, 𝑣) blue
UNION(𝑢, 𝑣)
od
return the tree formed by blue edges

此外,MAKE-SET(x)、UNION(x, y) 和 FIND(x) 定义如下:

MAKE-SET(𝒙)
Create a new tree rooted at 𝑥
PARENT(𝑥)=x

UNION(𝒙, 𝒚)
PARENT FIND(𝑥) ≔ 𝐹𝐼𝑁𝐷(𝑦)

FIND(𝒙)
𝑦 ≔ 𝑥
while 𝑦 ≠ PARENT(𝑦) do
𝑦 ≔ PARENT(𝑦)
return y

我现在遇到的问题是,虽然我可以在线性时间内实现 Kruskal 的前两行,但我还没有设法为算法的后四行做同样的事情(从 'for edge u, ...' 直到 'UNION (u, v)')。

对于如何在线性时间内实现算法的其余部分,或者如何在线性时间内找到 Kruskal 算法(或其他一些最小生成树算法)的修改,我将不胜感激。

谢谢。

最佳答案

如果您使用 Disjoint Sets data structure with both path compression and union by rank ,你会得到一个数据结构,它的每个操作的复杂性增长得非常缓慢——它有点像 Ackermann function 的倒数。 ,并且对于诸如宇宙中估计的原子数之类的尺寸来说并没有那么大。实际上,每个操作都被认为是常数时间,因此算法的其余部分也被认为是线性时间。

来自同一篇维基百科文章

Since α(n) is the inverse of this function, α(n) is less than 5 for all remotely practical values of n. Thus, the amortized running time per operation is effectively a small constant.

关于algorithm - 设计一种算法,在线性时间内找到该图的最小生成树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35727617/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com