HaskellでMSTアルゴリズム（PrimまたはKruskal）を書くにはどうすればよいですか？

Question

C++やJavaで最小スパニングツリーを見つけるために、PrimとKruskalの両方のアルゴリズムを書くことができますが、O（mlogm）やO（mlogn）（純粋な関数型プログラムが良い）でHaskellで実装する方法を知りたいと思います。どうもありがとう。

Answer 1

svenningssonが示すように、priority search queueは両方クラスカルのとプリムのに適しています（少なくとも著者は彼のpaperでそれを宣言する。）クラスカルの問題は、それはあなたがO（n個のログ）union-find algorithmを持っていることを必要とすることです。純粋に機能的なインタフェースを持つユニオン検索データ構造は、hereと記述されていますが、内部的に可変状態を使用しており、純粋に機能的な実装は不可能であり、実際には、効率的な純粋に機能的な解決策が知られていないthis関連の質問です。

非純粋なalterenativeは、STモナドでunion-findアルゴリズムを実装することです。 Hackageを検索すると、equivalenceパッケージが私たちのニーズに合っていることがわかります。

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)] 

equivalenceパッケージからData.Equivalence.Monadを使用してクラスカルの実装は次のとおり実行時間はO（1）時間で実行されている重みに依存しますが、fromLはO（log（n））時間で実行する重み関数を作成します。このc配列を使ってO（1）時間に改善するか、入力リストの重みを追跡するだけですが、実際にはアルゴリズムの一部ではありません。

Answer 2

私はあなたが探しているものが優先順位検索キューだと思います。これは、ラルフ・ヒンゼ（Ralf Hinze）が示したように、a paperの関数言語で最適に実装できます。この論文は、acmのライブラリを介してのみ利用可能であるようです。

Answer 3

ここには、粗い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の実装では、[更新]

...多分誰かがアイデアを持っている、

を、このためのより高速な解決策を見つけることができませんでした、残念ながらそれは変更可能なセットを使用しており、これをハスケルにどのように翻訳するのかわかりません。コードは私のブログにあります（申し訳ありませんが、説明はドイツ語です）：http://dgronau.wordpress.com/2010/11/28/nochmal-kruskal/