CODEWITHSUNDEEP
haskellprims-algorithm
troubledstudent
troubledstudent

Reputation:

Haskell Prim's Algorithm

does anyone know how the change prim's algorithm so that is handle a graph that is not connected? I know I have to use a forest but I don't know how to implement that in Haskell..

Upvotes: 0

Views: 954

Answers (3)

troublestudent
troublestudent

Reputation: 11

`This is what I got 

prim for            = prim' [n] ns [[]]
    where (n:ns)    = nodes for
        es          = edges for
        prim' t [] mst        = mst
        prim' t (r:rs) (x:xs) = let m = minimum[(c,u',v'| u <-t, v <- (r:rs), (u,v,c) <- es]
                    m | m == Nothing    = prim' (r:t) rs ([]:mst)
                      | otherwise       = prim' (v:t) (delete v' r) ((m:x):xs)

Upvotes: 1

Landei
Landei

Reputation: 54584

It's easy to find the connected parts of the graph. Run Prim's algorithm for every connected sub-graph separately.

Upvotes: 0

Doboy
Doboy

Reputation: 11092

Prim's algorithm finds a MST, but if the graph is not connected no MST exist. You can check if your tree is a spanning tree if it has |V| - 1 elements it in.

Upvotes: 0

Related Questions