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

Question

Ich kann Prims und Kruskals Algorithmen schreiben, um einen minimalen Spannbaum in C++ oder Java zu finden, aber ich möchte wissen, wie man sie in Haskell mit O (mlogm) oder O (mlogn) implementiert (reine Funktionsprogramme sind besser). Danke vielmals.

Answer 1

Wie Svenningsson schon sagt, ist priority search queue gut geeignet sowohl für Kruskals und Prim (atleast der Autor verkündet er in seiner paper.) Das Problem mit Kruskal ist, dass es erfordert, dass Sie einen O haben (log n) union-find algorithm. Eine Union-find-Datenstruktur mit einer rein funktionalen Schnittstelle wird here beschrieben, verwendet jedoch intern einen änderbaren Zustand, und eine rein funktionale Implementierung ist möglicherweise unmöglich, und tatsächlich gibt es mehrere Probleme, bei denen eine effiziente rein funktionale Lösung nicht bekannt ist this Verwandte SO Frage.

Eine nicht-reine Alternative ist die Implementierung von union-find-Algorithmus in der ST-Monade. Eine Suche auf Hackage findet, dass das equivalence Paket unseren Bedürfnissen entspricht. Es folgt eine Implementierung von Kruskal mit Data.Equivalence.Monad aus dem equivalence 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 sollte angemerkt werden, dass die Laufzeit von Gewichten abhängig ist, die in O (1) Zeit laufen, jedoch erzeugt fromL eine Gewichtungsfunktion, die in O (log (n)) Zeit läuft, dies c Eine Verbesserung auf O (1) Zeit durch die Verwendung von Arrays oder einfach das Gewicht in der Input-Liste zu verfolgen, aber es ist nicht wirklich Teil des Algorithmus.

Answer 2

Ich denke, eine Prioritätssuchwarteschlange ist, was Sie suchen. Es kann optimal in einer funktionalen Sprache implementiert werden, wie von Ralf Hinze in a paper demonstriert. Es scheint, als ob die Zeitung nur gegen eine Gebühr in der Bibliothek von acm erhältlich ist.

Answer 3

Hier ist eine grobe Kruskal-Implementierung.

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) ist. Das Problem besteht darin, eine schnellere Suche nach den Scheitelpunktgruppen in der Extraktfunktion zu finden. Ich konnte nicht eine schnellere Lösung hierfür finden, vielleicht jemand eine Idee ...

[Update]

Für eine Scala Implementierung I hat eine kartenähnliche Datenstruktur für (hoffentlich) verwenden eine bessere Leistung, aber leider verwendet es veränderbare Sätze, und ich habe keine Ahnung, wie man das in Haskell übersetzt. Der Code ist in meinem Blog: http://dgronau.wordpress.com/2010/11/28/nochmal-kruskal/