Minimum Spanning Tree - Kruskall's Algorithm
(Page 2 of 4 )
The best solution for our road system will be the minimal spanning tree. This is defined for graphs with no directed edges inside them. Therefore, if we find the correct n-1 edges (recall the rule that a tree with n edges will have exactly n-1 edges), we will have a road from all vertexes to all others, with the minimal cost between them.
The algorithm relies on a simple idea. We compile a list in ascending order of the edges based on their weight/distance/niceness (in the future we will refer to them only as weight). Now we kick off with a clean graph, from which we remove all the edges.
The idea is to now take all the edges in this increasing order and add n-1 number of edges in such a manner that we do not form a circle. In a tree, there will be no circle, so if we want to avoid having this happen, the problem is solved. The tree has no directed edges inside it; therefore, we can form a circle only if we add an edge to a couple of nodes, both of which are already corrected to an edge.
For optimal performance, we are going to resolve this problem by first assigning to each of the vertexes a different identification number (made up of their vertex number). We will perceive each node first as a member of a different tree. Adding new edges between these trees will result in the integration of one tree into another.
This way we can add an edge to the minimal spanning tree only if the two ends are members of a different tree. Systematically, we are going to melt one tree into another, and in the end, we are going to have a single tree. This will be the minimal spanning tree. Add up the weight of the edges that are members of the tree, and you will have the overall cost of the minimal spanning tree as well.
It is quite easy to understand and to program. The only detail left is how we are going to sort the tree. I decided to call the qsort function residing inside the libraries of C. For this, we also need to write a function comparing the two edges. I've included that as well. Study both of them:
int compareEdges(const void* edge1, const void * edge2)
{
pEdge first = (pEdge)edge1;
pEdge second = (pEdge)edge2;
return first->weight - second->weight;
}
void Kruskal ()
{
int i = 0, overallWeight = 0, j =0;
int fromTree = 0, toTree = 0, changeNr = 0;
// sort the edge list
qsort ((void*) edges, m, sizeof (Edge), compareEdges);
printf ("n");
print ();
printf ("n");
printf ("nThe list of the edges with the algorithm of Kruskall:n");
// build up the individual list
for ( i =1; i <= n; ++i)
tree[i] = i;
for ( i= 0; i < m && changeNr < n; ++i)
{
fromTree = tree[edges[i].from];
toTree = tree[edges[i].to];
if( fromTree != toTree)
{
++changeNr;
overallWeight += edges[i].weight;
printf(" %d) %d ~ %d -> %d n", changeNr, edges[i].from, edges[i].to, edges[i].weight);
//Union of the trees
for ( j = 0; j < m; ++j)
if(tree[j] == toTree)
tree[j] = fromTree;
}
}
printf( " n The minimal weight %d ", overallWeight);
}
Next: Prim's Technique >>
More Code Examples Articles
More By Gabor Bernat
/ 5 
