How can I write a MST algorithm (Prim or Kruskal) in Haskell?

Question

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.

Answer 1

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.

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

It can be used like this:

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

and running test gives:

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

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.