Minimum Spanning Tree (Prim algorithm and Kruskal algroithm)

Prim algorithm is a greedy approach, it is quite similar to Dijkstra algorithm)

The algorithm goes as follows:

1.Mark all nodes with a cost and a parent (i.e. in an array).
2.The source node has a cost of 0 and all other node has cost of infinity.
3.While there is an unvisited node in the graph do
pick the node with the smallest cost, mark it as visited.
update all its unvisited neighbor if the cost of that neighbor is less than the cost of the current node + the edge between the current node and that neighbor. Also update the parent of the neighboring node to current node if the cost of that neighbor is updated
if the current node has a parent, push the edge of current node and its parent into the result.

This is a greedy algorithm. The running time is O(ElogV), picking the smallest cost node is logV for each vertex, we need to visit all its neighboring edges.

The other algorithm that also developed the MST is the kruskal’s algorithm, this algorithm focus on edges instead of vertices. It uses a simpler data structure Disjoint-set. The algorithm goes as follows:

1. sort all the edges in the order of weight.
2. pick the smallest of all the edges, create a set that contains two ends, if the set not in the result, merge it into the result set. else skip.
3. repeat 2 until all the vertices are in the result.

The running time is ElogE.

So it depends on the application, if graph is a sparse graph, meaning the number of edges are small, then the kruskal’s algorithm is faster (this is also the common case), otherwise if the graph is dense, then the prim’s algorithm is faster.

Leave a Reply

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

You are commenting using your 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