Minimum Spanning Tree - Prim's Technique
(Page 3 of 4 )
Kruskall's algorithm can already solve our problem. However, there exists a different solution to this, initially formed by Vojtech Jarník in 1930 and later rediscovered by Robert C. Prim in 1957. The approach is different and the complexity of the algorithms is different.
Kruskall's algorithm, coded with the previously-shown solution to avoid the formation of circles, has a complexity of O( m*log(m)) together with the sort. On the other hand, if we code with a binary heap (which is a lot of work to do), it may yield a complexity of only (( m*log(n)). So if you invest a little effort, this solution may run faster. The theory is also a bit more complicated.
You could already see the greedy traits in Kruskall's algorithm; this technique will behave in the same manner. Now, instead of constructing multiple trees at the same time, we will start from a root vertex and build a tree with the root item being that specific node.
At every step, we will increase it with the minimal edge relating to the current tree. The edge related to the tree is composed of the edges that have exactly one node as the member of the tree. This way, for each time, we will have added another edge that is related to the current tree, and after n-1 steps our tree is complete.
What we need to resolve is the inclusion and exclusion of edges inside this list from where we are going to find the next smallest edge. I opted for the following solution. First, I sorted the edges into an increasing order. Second, I added another trait to the edges in the edge list.
Finally, after we add another vertex to the tree (via the add root, or find another good minimal edge), we need to remove the edges that go inside the tree -- that is, both edges are inside the tree -- and add those that will come with the addition of the new vertex. The edges from which we are going to choose the next/minimal edge are the ones that connect our current tree with the rest of the graph. This way, they can be perceived as the ones standing in the cut of our tree and the graph.
I will only change the value of whether or not an edge is within this cut, by setting the inTheCut trait of the edge to false or true. Finally, we will choose the first inTheCut edge from the list, as this will be minimal, because our list is sorted in ascending order.
Adding up the weight of the edges that make up the tree is child's play, so in the end we may print out the weight of the minimal spanning tree. This is what interests us if we are building that road. This can represent the distance in miles that we need to construct, the money that it will cost, and so on, based on what we input as weight.
Next: Prim's Algorithm in C >>
More Code Examples Articles
More By Gabor Bernat
/ 5 
