Wie kann ich einen MST-Algorithmus (Prim oder Kruskal) in Haskell schreiben?

Question

kann ich beide Prims und Kruskals Algorithmen schreiben ein Minimum zu finden Spanning Tree in C ++ oder Java, aber ich möchte wissen, wie sie mit O (mlogm) oder O (mlogn) (rein funktionale Programme ist besser) in Haskell implementieren . Vielen Dank.

Answer 1

Wie Svenningsson schon sagt, Priorität Suche Warteschlange ist gut für beide Kruskals und Prim (atleast der Autor proklamiert es in seiner Papier .) Das Problem mit Kruskal ist, dass es erfordert, dass Sie einen O (log n) Union-Find-Algorithmus . Eine Union-Find-Datenstruktur mit einem rein funktionalen Schnittstelle hier , aber es intern verwendet wandelbar Zustand, und eine rein funktionale Umsetzung könnte unmöglich sein, und in der Tat gibt es einige Probleme, bei denen eine effizienten rein funktionale Lösung nicht bekannt ist, wie in diese verwandten SO Frage.

Ein nicht rein alterenative ist Union-Find-Algorithmus in der ST-Monade zu implementieren. Eine Suche auf Hackage findet, dass die Äquivalenz Paket unseren Bedürfnissen entspricht. Es folgt eine Implementierung von Kruskal mit Data.Equivalence.Monad aus dem Äquivalenz Paket:

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

Es kann wie folgt verwendet werden:

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

und Lauftest ergibt:

[(1,2),(1,3),(3,4)]

Es ist zu beachten, dass die Laufzeit für die Gewichte abhängig ist in O (1) verlauf Zeit jedoch fromL erzeugt eine Gewichtsfunktion in O läuft (log (n)) der Zeit kann dies zu O verbessert werden (1) Zeit von Arrays oder das Gewichts in der Eingangsliste zu verfolgen, aber es ist nicht wirklich Teil des Algorithmus.

Answer 2

Dies ist eine grobe Kruskal Umsetzung.

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

Der erste Schritt ist das Sortieren der Kanten, die O (n log n). Das Problem ist ein schneller Nachschlag für die Eckenmengen in der Extrakt-Funktion zu finden. Ich konnte nicht eine schnellere Lösung für diese, vielleicht hat jemand eine Idee finden ...

[Update]

Für eine Scala Implementierung verwendete ich eine kartenähnliche Datenstruktur für (hoffentlich) eine bessere Leistung, aber leider nutzt es wandelbar Sets, und ich habe keine Ahnung, wie dies in Haskell zu übersetzen. Der Code ist in meinem Blog (leider Beschreibung ist in deutscher Sprache): http: / /dgronau.wordpress.com/2010/11/28/nochmal-kruskal/

Answer 3

Ich denke, eine Priorität Suche Warteschlange ist das, was Sie suchen. Es kann optimal in einer funktionalen Sprache implementiert werden, wie von Ralf Hinze demonstriert in ein Papier . Es scheint, wie das Papier über acm Bibliothek zu einem Preis verfügbar ist.