Programming Praxis – Minimum Spanning Tree: Prim’s Algorithm

In today’s Programming Praxis exercise we have to implement an algorithm for finding the minimum spanning tree of a graph. The Scheme solution weighs in at 15 lines, so let’s see if we can do better.

As usual, some imports:

import Data.List
import qualified Data.List.Key as K

Both the Scheme solution and the pseudocode algorithm on Wikipedia take both a list of vertices and a list of edges as input, but since the list of vertices is implicitly defined in the edges there's really no point in specifying it separately. To get the starting vertex, we just take the first vertex of the first edge. Other than that, we do pretty much what the pseudocode algorithm says: check if there's an edge with one connected and one unconnected point. If multiple exist, add the shortest. Add the unconnected vertex to the list of connected ones. Stop if there are no more edges with unconnected vertices.

prim :: (Eq a, Ord b) => [(a, a, b)] -> [(a, a, b)]
prim es = f [(\(v,_,_) -> v) $ head es] [] where
    f vs t = if null r then t else f (union vs [x,y]) (m:t) where
        r = filter (\(a,b,_) -> elem a vs /= elem b vs) es
        m@(x,y,_) = K.minimum (\(_,_,c) -> c) r

A quick test shows we get the same result as the Scheme version:

main :: IO ()
main = print $ prim [('A', 'D',  5), ('A', 'B', 7), ('B', 'D', 9)
                    ,('B', 'C',  8), ('C', 'E', 5), ('B', 'E', 7)
                    ,('D', 'E', 15), ('D', 'F', 6), ('E', 'F', 8)
                    ,('F', 'G', 11), ('E', 'G', 9)]

And with that we've reduced a 15-line solution to four lines. Not bad.

About these ads

Tags: , , , , , , , , , ,

3 Responses to “Programming Praxis – Minimum Spanning Tree: Prim’s Algorithm”

  1. JackeLee Says:

    Yea, your solution is 4-line length, but runs in O(|V| * |E|^2), where E is set of edges and V set of verticles. This is not good.

  2. Remco Niemeijer Says:

    Oh, I have no doubt that more efficient algorithms exist. However, in my programming in general and this blog in particular, my primary focus is simple (which often equates to short) code. Only when performance becomes a problem do I start looking at more efficient algorithms, which have a tendency to be longer and more complicated. In this case, the test data was so small that the extra effort was not warranted.

  3. JackeLee Says:

    No, there is nothing wrong with Jarnik-Prim algorithm, in imperative language one can implement it in O(|E| + |V| * log(|V|)). You just don’t use any data structure to increase speed, instead you search the same list again and again to find what you need ;-).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: