Minimum Spanning Tree - Prim's Algorithm in C
(Page 4 of 4 )
Here it is the code snippet for what I tried to explain on the previous page:
int Prim(int at)
{
int i = 0;
memset(tree, 0, (n+1)*sizeof(int));
tree[at] = 1;
ancient[at] = 0 ;
// sort the edge list
qsort((void*)edges,m,sizeof(Edge),compareEdges);
// build up the tree
for (i = 0; i < m; ++i)
{
distanceMatrix[edges[i].from][edges[i].to ] = i;
distanceMatrix[edges[i].to ][edges[i].from] = i;
if (edges[i].from == at || edges[i].to == at)
{
edges[i].inTheCut = true;
}
else
{
edges[i].inTheCut = false;
}
}
int overallWeight = 0;
int curent = 0;
int addedVertex = 1;
int neighborVertex = 0;
int neighborEdge = 0;
pListIt p = NULL;
int j = 0;
for(i = 1; i < n; ++i)
{
for ( j =0 ; j < m; ++j)
{
if (edges[j].inTheCut)
{
curent = j;
break;
}
}
printf( " %d) %d ~ %d -> %d n",
i, edges[curent].from, edges[curent].to, edges[curent].weight);
overallWeight += edges[curent].weight;
if (tree[edges[curent].from] == 1)
{
addedVertex = edges[curent].to;
ancient[addedVertex] = edges[curent].from;
}
tree[addedVertex] = 1;
for (p = adjacencyList[addedVertex]; p != NULL;
p = p -> p_next)
{
neighborVertex = p->value;
neighborEdge = distanceMatrix[addedVertex][neighborVertex];
if (tree[neighborVertex] == 1)
// reset if both ends are there
edges[neighborEdge].inTheCut = false; else
// set if only one is there
edges[neighborEdge].inTheCut = true;
}
}
printf( "nn The overall Weight: %d " , overallWeight);
return 0;
}
From the following link you can see this encapsulated into a working C file that, after you compile it you can execute it, test it and see if you can improve it. It is painlessly commented, so if you feel like doing some homework in coding, you'll be able to understand it with no effort, even without this article.
-->Minimum Spanning Tree.zip<--
I invite you to rate my article or express your ideas, questions and other thoughts you may have here on the blog for the article. If you want, you may also join our friendly and ever-growing forum at DevHardware. Here our experts will eagerly answer your questions, whatever they may be. During our next meeting with graphs, I am going to present how to calculate the minimal distances between points inside a graph. Until that time arrives, Live With Passion!
| DISCLAIMER: The content provided in this article is not warranted or guaranteed by Developer Shed, Inc. The content provided is intended for entertainment and/or educational purposes in order to introduce to the reader key ideas, concepts, and/or product reviews. As such it is incumbent upon the reader to employ real-world tactics for security and implementation of best practices. We are not liable for any negative consequences that may result from implementing any information covered in our articles or tutorials. If this is a hardware review, it is not recommended to open and/or modify your hardware. |
