Minimum Spanning Tree
(Page 1 of 4 )
At some portions in our life we arrive at a situation where it is no longer enough to be average, or to perform at an average rate. In order to succeed we need to bring forth the best solution possible from the circumstances. If this means finding the shortest spanning tree inside something that may be represented as a graph, then you've come to the right place. Today, we are going to examine two techniques to achieve this: Kruskall’s and Prim’s.
Before we venture more deeply into the waters of minimal spanning trees, I would like to remind you that this article is part of a larger series I am writing about graphs, and I invite you to read the rest of them if you are interested. Each article presents a set of new techniques to resolve a particular problem. It is also illustrated with code snippets written in C. This article is the seventh part of a 13-part series.
Strictly speaking, if you want to understand this article, only the first article in this series, An Insight into Graphs, is needed. It will explain what graphs are, why we use them, and how we incorporate them into a coding language. For now, let us discuss minimal spanning trees, shall we?
Until now we've treated the trees only from the point of view of whether or not there exists an edge between two vertexes. We used the adjacent matrix or the edge list, and sometimes the adjacent list, to represent this. Nevertheless, the edges do not have the same traits all the time.
We may like a few of them more, and even build a list of how favorable each one of them is for us. This idea stems from day-to-day problems. For instance, we may want to build the road system of a country. Now we do not have the money to construct a road between all of the cities, so the idea is to construct a system that allows us to spend the least amount of money (it is a world crisis, remember?).
If we are on a plane (i.e. the country is completely flat), then all we need to take into account is the distance. Then again, if the country has some mountains, we also need to consider how much each road would cost to build between the cities. This way we can assign weights to the edges. Storing them is usually done in two ways. The first solution is simply to add another member to the edge list, that we can call intuitively the weight of the edge.
The second one is to build the weight/distance/niceness matrix of the graph. Here we will store at position "i" "j" the weight/distance/niceness of the edge, and otherwise infinity. Since we are limited to a maximal number in programming, we are going to use INT_MAX/2, assuring for us that adding infinity with infinity will be still a positive number. The closer to the best an edge is in the rank of weight/ distance/niceness, the closer it will be to the number 0 (or the more negative it is).
Next: Kruskall's Algorithm >>
More Code Examples Articles
More By Gabor Bernat
