如何在Haskell中编写MST算法（PRIM或KRUSKAL）？

Question

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

Answer 1

正如Svenningsson所建议的那样 优先搜索队列 非常适合Kruskal和Prim's（作者至少在他的 纸。 Union-Find算法. 。描述了具有纯粹功能接口的联合信息数据架构 这里, ，但是它在内部使用可变状态，并且纯粹的功能实现可能是不可能的，实际上，在几个问题中，尚不清楚有效的纯粹功能解决方案，如 这 相关的问题。

非纯化的替代性是在圣单元中实施联合获取算法。搜索骇客发现 等价 包装适合我们的需求。以下是使用data.Equilence.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）时间，但这并不是算法的一部分。

Answer 2

这是一个粗略的克鲁斯卡尔实施。

import Data.List(sort)
import Data.Set (Set, member, fromList, insert, union)

data Edge a = Edge a a Double deriving Show

instance (Eq a) => Eq (Edge a) where
  Edge x1 y1 z1 == Edge x2 y2 z2 = x1 == x2 && y1 == y2 && z1 == z2

instance Eq a => Ord (Edge a) where
  (Edge _ _ x) `compare` (Edge _ _ y) = x `compare` y

kruskal :: Ord a => [Edge a] -> [Edge a]
kruskal = fst . foldl mst ([],[]) . sort

mst :: Ord a => ([Edge a],[Set a]) -> Edge a -> ([Edge a],[Set a])
mst (es, sets) e@(Edge p q _) = step $ extract sets where
   step (rest, Nothing, Nothing) = (e : es, fromList [p,q] : rest)
   step (rest, Just ps, Nothing) = (e : es, q `insert` ps : rest)
   step (rest, Nothing, Just qs) = (e : es, p `insert` qs : rest)
   step (rest, Just ps, Just qs) | ps == qs = (es, sets) --circle
                                 | otherwise = (e : es, ps `union` qs : rest)
   extract = foldr f ([], Nothing, Nothing) where
       f s (list, setp, setq) =
            let list' = if member p s || member q s then list else s:list
                setp' = if member p s then Just s else setp
                setq' = if member q s then Just s else setq
            in (list', setp', setq') 

第一步是对边缘进行排序，即o（n log n）。问题是要在提取功能中找到更快的查找顶点集。我找不到更快的解决方案，也许有人有一个想法...

更新

对于Scala实现，我使用了类似地图的数据结构来进行（希望）更好的性能，但不幸的是它使用了可变的集合，而且我不知道如何将其转化为Haskell。该代码在我的博客中（对不起，描述是德语）： http://dgronau.wordpress.com/2010/11/28/nochmal-kruskal/

Answer 3

我认为优先搜索队列是您想要的。它可以用Ralf Hinze在功能语言中最佳实现 一篇论文. 。看来该论文只能通过ACM的图书馆提供。