如何在Haskell中编写MST算法(Prim或Kruskal)? [英] How can I write a MST algorithm (Prim or Kruskal) in Haskell?

问题描述

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

I can write both Prim's and Kruskal's algorithms to find a minimum spanning tree in C++ or Java, but I want to know how to implement them in Haskell with O(mlogm) or O(mlogn) (pure functional programs is better). Thanks a lot.

推荐答案

如svenningsson所建议的，纸张.)Kruskal的问题在于，它要求您有一个O(log n)联盟查找算法.在此处中描述了具有纯功能接口的联合查找数据结构.在内部使用可变状态，并且纯功能的实现可能是不可能的，实际上，存在一些问题，其中不存在有效的纯功能解决方案，如在

As svenningsson suggests, priority search queue is well suited for both Kruskal's and Prim's (atleast the author proclaims it in his paper.) The problem with Kruskal is that it requires that you have an O(log n) union-find algorithm. A union-find datastructure with a purely functional interface is described here, but it uses mutable state internally, and a purely functional implementation might be impossible and in fact, there are several problems where an efficient purely functional solution is not known, as discussed in this related SO question.

一个非纯的替代方法是在ST monad中实现联合查找算法.对Hackage的搜索发现，等效性软件包符合我们的需求.以下是来自 equivalence 包中的Data.Equivalence.Monad的Kruskal实现:

A non-pure alterenative is to implement union-find algorithm in the ST monad. A search on Hackage finds that the equivalence package suits our needs. Following is an implementation of Kruskal using Data.Equivalence.Monad from the equivalence package:

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) )通过使用数组或仅跟踪输入列表中的权重来进行计时，但这并不是算法的真正组成部分.

It should be noted that the running time is dependent on weights running in O(1) time, however fromL creates a weight function running in O(log(n)) time, this can be improved to O(1) time by using arrays or just keeping track of the weight in the input list, but it's not really part of the algorithm.

这篇关于如何在Haskell中编写MST算法(Prim或Kruskal)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！