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

Question

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

Answer 1

正如svenningsson建议的那样, 优先搜索队列非常适合Kruskal和Prim(至少作者在他的论文中宣称它.)Kruskal的问题是它需要你有一个O(log n)联合查找算法.这里描述了一个带有纯功能接口的联合查找数据结构,但是它在内部使用了可变状态,并且纯粹的功能实现可能是不可能的,事实上,有几个问题,其中一个有效的纯功能解决方案是未知的,如这个相关的SO问题.

非纯粹的替代是在ST monad中实现union-find算法.对Hackage的搜索发现等价包适合我们的需求.以下是使用等价包中的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)时间.只是跟踪输入列表中的权重,但它并不是算法的一部分.

Answer 2

这是一个粗糙的Kruskal实现.

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/