haskell - 如何在 Haskell 中编写 MST 算法(Prim 或 Kruskal)？

我可以编写 Prim 和 Kruskal 的算法来在 C++ 或 Java 中找到最小生成树，但我想知道如何在 Haskell 中使用 O(mlogm) 或 O(mlogn) 实现它们(纯函数程序更好)。非常感谢。

最佳答案

正如 svenningsson 所建议的那样，priority search queue 非常适合 Kruskal 和 Prim(至少作者在他的 paper 中声明)。Kruskal 的问题在于它要求你有一个 O(log n) union-find algorithm 。 here 描述了具有纯函数接口(interface)的 union-find 数据结构，但它在内部使用可变状态，纯函数实现可能是不可能的，事实上，存在几个问题，其中不知道有效的纯函数解决方案，如在this 相关的 SO 问题。

一个非纯粹的替代方案是在 ST monad 中实现联合查找算法。在 Hackage 上搜索发现 equivalence 包适合我们的需求。以下是使用 equivalence 包中的 Data.Equivalence.Monad 的 Kruskal 实现:

import Data.Equivalence.Monad
import Data.Graph as G
import Data.List(sortBy)
import Data.Map as M
import Control.Monad(filterM)
import Data.Ord(comparing)

run = runEquivM (const ()) (const $ const ())

kruskal weight graph = run $
 filterM go (sortBy (comparing weight) theEdges)
     where
      theEdges = G.edges graph
      go (u,v) = do
        eq <- equivalent u v
        if eq then return False else
         equate u v >> return True

它可以像这样使用:

fromL xs = fromJust . flip M.lookup (M.fromList xs)

testWeights = fromL [((1,2),1),((2,3),4),((3,4),5),((1,4),30),((1,3),4)]
testGraph = G.buildG  (1,4) [(1,2),(2,3),(3,4),(1,4),(1,3)]
test = kruskal testWeights testGraph

并运行测试给出:

[(1,2),(1,3),(3,4)]

需要注意的是，运行时间取决于在 O(1) 时间内运行的权重，但是 fromL 创建了一个在 O(log(n)) 时间内运行的权重函数，这可以通过使用数组改进到 O(1) 时间或者只是跟踪输入列表中的权重，但这并不是算法的真正组成部分。

关于haskell - 如何在 Haskell 中编写 MST 算法(Prim 或 Kruskal)？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4290163/