如何在Haskell中编写MST算法(PRIM或KRUSKAL)?
-
28-09-2019 - |
题
我可以编写Prim和Kruskal的算法,以在C ++或Java中找到最小的生成树,但是我想知道如何使用O(MLOGM)或O(MLOGN)在Haskell中实现它们(纯函数程序更好)。非常感谢。
解决方案
正如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)时间,但这并不是算法的一部分。
其他提示
这是一个粗略的克鲁斯卡尔实施。
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/
我认为优先搜索队列是您想要的。它可以用Ralf Hinze在功能语言中最佳实现 一篇论文. 。看来该论文只能通过ACM的图书馆提供。