In this article I give an informal definition of a graph and of the minimum spanning tree. Afterwards I describe Prim’s algorithm and then follow its execution on an example. Finally, the code in C is provided.
Graphs
Wikipedia gives one of the common definitions of a graph:
In computer science, a graph is a kind of data structure, specifically an abstract data type (ADT), that consists of a set of nodes and a set of edges that establish relationships (connections) between the nodes. The graph ADT follows directly from the graph concept from mathematics.
Informally, G=(V,E) consists of vertices, the elements of V, which are connected by edges, the elements of E. Formally, a graph, G, is defined as an ordered pair, G=(V,E), where V is a finite set and E is a set consisting of two element subsets of V.
This is a graph:
It’s a set of nodes (A, B, C, D and E) and the edges (lines) that interconnect them.
An important thing to note about this graph is that the edges are bidirectional, i.e. if A is connected to B, then B is connected to A. This makes it an undirected graph.
A common extension is to attribute weights to the edges. This is what I’ve done with the previous graph:
Minimum spanning trees
Basically a minimum spanning tree is a subset of the edges of the graph, so that there’s a path form any node to any other node and that the sum of the weights of the edges is minimum.
Here’s the minimum spanning tree of the example:
Look at the above image closely. It contains all of the initial nodes and some of the initial edges. Actually it contains exactly n – 1 edges, where n is the number of nodes. It’s called a tree because there are no cycles.
You can think of the graph as a map, with the nodes being cities, the edges passable terrain, and the weights the distance between the cities.
It’s worth mentioning that a graph can have several minimum spanning trees. Think of the above example, but replace all the weight with 1. The resulting graph will have 6 minimum spanning trees.
Given a graph, find one of its minimum spanning trees.
Prim’s Algorithm
One of the classic algorithms for this problem is that found by Robert C. Prim. It’s a greedy style algorithm and it’s guaranteed to produce a correct result.
In the following discussion, let the distance from each node not in the tree to the tree be the edge of minimal weight between that node and some node in the tree. If there is no such edge, assume the distance is infinity (this shouldn’t happen).
The algorithm (greedily) builds the minimal spanning tree by iteratively adding nodes into a working tree:
- Start with a tree which contains only one node.
- Identify a node (outside the tree) which is closest to the tree and add the minimum weight edge from that node to some node in the tree and incorporate the additional node as a part of the tree.
- If there are less then n – 1 edges in the tree, go to 2
For the example graph, here’s how it would run:
Start with only node A in the tree.
Find the closest node to the tree, and add it.
Repeat until there are n – 1 edges in the tree.
The Programme
The following programme just follows the algorithm. It runs in O(n2) time.
Here’s the code in C (prim.c):
#include <stdio.h>
/*
The input file (weight.txt) look something like this
4
0 0 0 21
0 0 8 17
0 8 0 16
21 17 16 0
The first line contains n, the number of nodes.
Next is an nxn matrix containg the distances between the nodes
NOTE: The distance between a node and itself should be 0
*/
int n; /* The number of nodes in the graph */
int weight[100][100]; /* weight[i][j] is the distance between node i and node j;
if there is no path between i and j, weight[i][j] should
be 0 */
char inTree[100]; /* inTree[i] is 1 if the node i is already in the minimum
spanning tree; 0 otherwise*/
int d[100]; /* d[i] is the distance between node i and the minimum spanning
tree; this is initially infinity (100000); if i is already in
the tree, then d[i] is undefined;
this is just a temporary variable. It's not necessary but speeds
up execution considerably (by a factor of n) */
int whoTo[100]; /* whoTo[i] holds the index of the node i would have to be
linked to in order to get a distance of d[i] */
/* updateDistances(int target)
should be called immediately after target is added to the tree;
updates d so that the values are correct (goes through target's
neighbours making sure that the distances between them and the tree
are indeed minimum)
*/
void updateDistances(int target) {
int i;
for (i = 0; i < n; ++i)
if ((weight[target][i] != 0) && (d[i] > weight[target][i])) {
d[i] = weight[target][i];
whoTo[i] = target;
}
}
int main(int argc, char *argv[]) {
FILE *f = fopen("dist.txt", "r");
fscanf(f, "%d", &n);
int i, j;
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
fscanf(f, "%d", &weight[i][j]);
fclose(f);
/* Initialise d with infinity */
for (i = 0; i < n; ++i)
d[i] = 100000;
/* Mark all nodes as NOT beeing in the minimum spanning tree */
for (i = 0; i < n; ++i)
inTree[i] = 0;
/* Add the first node to the tree */
printf("Adding node %c\n", 0 + 'A');
inTree[0] = 1;
updateDistances(0);
int total = 0;
int treeSize;
for (treeSize = 1; treeSize < n; ++treeSize) {
/* Find the node with the smallest distance to the tree */
int min = -1;
for (i = 0; i < n; ++i)
if (!inTree[i])
if ((min == -1) || (d[min] > d[i]))
min = i;
/* And add it */
printf("Adding edge %c-%c\n", whoTo[min] + 'A', min + 'A');
inTree[min] = 1;
total += d[min];
updateDistances(min);
}
printf("Total distance: %d\n", total);
return 0;
}
And here’s a sample input file (dist.txt). It’s the example graph:
5
0 10 0 5 0
10 0 5 5 10
0 5 0 0 0
5 5 0 0 20
0 10 0 20 0
The code’s commented and there shouldn’t be any problems.
Good luck. Always open to comments.
2007-12-05 at 21:19
Programming Tutorials
I couldn’t understand some parts of this article, but it sounds interesting
2008-03-05 at 19:17
i try to execute the code but there is a mistake with the code
also i couldnt understand this lines in the code
{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
int main(int argc, char *argv[]) {
FILE *f = fopen(“dist.txt”, “r”);
fscanf(f, “%d”, &n);
int i, j;
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
fscanf(f, “%d”, &weight[i][j]);
fclose(f);
2010-05-03 at 11:38
you are donkey or stupit,you have nothing to do?
2012-07-17 at 5:34
You cann’t say like that. It represents yourself. fool…….
2008-03-10 at 22:42
[…] this site Minimum Spanning Trees: Prim’s Algorithm « Computer programming __________________ http://www.vbuniverse.com Blog for latest […]
2008-03-11 at 15:38
Source is so helpful to me. Thank you…
2008-04-15 at 22:38
thank you thats very helpful, and its awe fully nice of you to make the effort to make it so easily understandable
2008-05-24 at 22:35
thanks alot it is very helpful
2008-06-01 at 11:09
Thanks very much, it’s very helpful, the first time i fully understand the MST :).
2008-07-01 at 1:39
Thanks… The source is very clear and nice to read
2008-07-15 at 19:34
I love You man. U saved me ^_^
2008-09-04 at 21:50
use “if ( !inTree[i] && (weight[target][i] != 0) && (d[i] > weight[target][i]))” instead of “if ( (weight[target][i] != 0) && (d[i] > weight[target][i]))” is better.
2010-10-16 at 21:36
I can confirm this is an error. Please fix it.
2008-11-11 at 4:42
Algorithm is nicely explained, very clear and lots of comments……
2008-11-17 at 18:42
thank u very much…if not full i understood something about this..
2008-11-22 at 8:25
“int main(int argc, char *argv[])”
It looks like you want to use command line to open the input file.
But, you assign the name of the input file here.
“FILE *f = fopen(“dist.txt”, “r”)”
So, just use “int main()” should be clear.
2008-12-11 at 6:26
i transfer this c to java code, there is problem with this code,
/* Find the node with the smallest distance to the tree */
int min = -1;
for (i = 0; i d[i]))
min = i;
this part need deep modification, other than that, this is good prim example to use. also WhoTo [], i still don’t know if i need that or not. i from pt of view, i think that array can be ignore. one more comment, after u change that code, the value of total at the end is need modify if u want total to show up right.
as i said this code is very helpful, but i had spend over 10 hr to make it right into java.
2009-06-10 at 17:22
for zzzz,
could u share with me a source code in java. i’m as a teacher want to share it with my students. ):
2015-10-09 at 0:19
Hi, could I please see your version of this in Java? As I would like to understand how to do this in Java. Also does it check if a cycle is created? Thank you. My email address is anum_n@hotmail.co.uk
2009-02-19 at 10:17
chup
vua codeeeeeeeeeeeeeeeeeeeeeeee
wrong code
disgusting code
it does not help me
2009-02-19 at 10:18
how much a code disgusting can be!!!!!!!!!
I cant imagine until I saw this code
2009-05-09 at 23:09
Thank you so much for this awesome code!
2009-05-09 at 23:09
And for the clear and well written explanations as well, of course! =)
2009-06-10 at 17:26
dear alex,
hi, i’m everything new in this topic, could you send a source code in java or c++. which compiler we have to use better? ):
2009-06-10 at 17:27
dear alex,
my emel is rosemizie@hotmail.com
god bless you if you can help me.
2009-06-10 at 17:19
does anybody hava a source code in java or c++.
2012-05-16 at 7:05
i have the java code please call me to this number +919032897206
2009-11-03 at 4:15
nice article.keep the good work up
2009-11-19 at 13:25
hi ,
I have tried ‘ prims ‘ c code in linux . compilation is OK . but while i run the code ,it shows segmentation fault .
Please give th solution ? so that the program will run !!!
2009-12-01 at 12:15
i don’t understand “int main(int argc, char *argv[])â€. please help me.
Thanks anyway!
good luck.
2010-03-18 at 10:01
can somebody explain how to use input file . i tried to run the program by copying the input file and typing the address of the file while input command but nothing happened. plz give explaination how to do it??
2010-03-23 at 16:14
this code is abs cool. thanks to the pgmr
2010-03-27 at 12:12
this code is very clearly and simply written,and the way it has been explained is awesome
2010-04-26 at 8:23
algorithm explained neatly…well done good job…….
2010-04-30 at 7:15
thanksssssssss
2010-06-06 at 17:18
hello. please email me a good article about prim algorithm or huffman algorithm.
2010-10-21 at 22:10
thanks for contents
2010-10-31 at 3:11
very good program, can anyone help me with parallel version of Prim’s method (using OpenMP, Win32 or POSIX)?
2010-11-12 at 16:38
very nice but i want a code not to start from node A to every nodes but to read a txt file like B-E. B is the node i want to start and E the end node. Sorry for my English :)
2010-11-23 at 16:51
ata na jata ,chunav chinha chhata,,,
ab se sahi programme likhna you donkey
2010-11-23 at 23:49
thanks alot for your code
2010-12-01 at 4:13
//You have to do corner case processing when min is -1
if(min != -1)
{
printf(“Adding edge %c-%c\n”, whoTo[min] + ‘A’, min + ‘A’);
inTree[min] = 1;
total += d[min];
updateDistances(min);
}
else
{
break;
}
2010-12-18 at 6:35
this code cannot check whether the graph is connected or not
2010-12-29 at 11:03
donde debo colocar el archivo dist para q el programa lo lea????
2011-02-01 at 6:59
i cant understand this
2011-03-26 at 8:51
i get a segmentation fault in this program
2011-04-13 at 5:16
thanks, it helps me a lot :)
2011-04-18 at 13:19
Please I would like to know how spanning trees are alike
2011-07-29 at 6:40
Does this code check for cycles ..And avoid them..Can u tell me in which part of this code its being done..!!
2011-08-27 at 6:43
very nice article….
u have solved my problem…
thankew…
2011-09-18 at 7:43
Hey friends…
I m SAPAN.
Plz send me the prims sudeo code at sapan.shah177@gmail.com…
Plz fast because tomorrow exam… So plz send me…..
2011-09-20 at 9:44
latest technologies…
[…]Minimum Spanning Trees: Prim’s Algorithm « Computer programming[…]…
2011-09-22 at 10:01
hiiiiiiiiiii
2011-10-06 at 14:36
DUDE, thank- you so very much man… it took me days but i finally cracked it :P
urs is probably the only perfectly working code for the algorithm…hats off dude…pls keep up the gr8..sry amazing work.
2011-10-17 at 16:57
great work bro!!!!!
2011-10-20 at 22:56
you are amazing!!! i have been two days trying to solve and your code will save me today…. thanks a lot
2011-11-06 at 0:51
socia’net for musicians…
[…]Minimum Spanning Trees: Prim’s Algorithm « Computer programming[…]…
2011-11-28 at 2:44
Thank you very much :) I appreciate loading from a file, amazing.
2011-11-30 at 4:11
thank you very much for sharing this lesson^^
2011-12-01 at 10:53
cheers!!
tanx a lottt
2011-12-02 at 5:27
thnx; its good enough…
2012-03-17 at 8:19
very clearly explained…
2012-04-05 at 8:20
THIS IS SO COMPLICATED CODE,,, TRY TO SIMPLE IT ,,,,,
2012-04-05 at 10:21
Does someone have this code in Matlab for me please? I need it for my Genetic Algorithm’s initial population because I’ve been struggling now for a long time and no one can help me please?
2012-04-16 at 17:27
sir if we want to find a minimum spanning tree for specific points e.g for three points then how to code this problem
2012-04-17 at 22:41
java code for freckles kruskal’s algorithm pleaseeeeee???
2012-05-09 at 23:36
Brilliant.
2012-07-04 at 7:50
thanks a lot! you saved my life!
We must to set the input file on the same place where the .cpp file is saved
Change your input text file in the code
2012-07-10 at 10:06
very nice,,,,
Thanks to all
2012-08-07 at 8:15
thnks
2012-09-04 at 17:41
jangbahaudr patel
it was a very nice stuff for me..
2012-10-06 at 8:10
gr8………..
2012-11-16 at 14:00
core java code for distance between one vertex to another vertex in weighted graph
2012-12-05 at 19:30
Thank you so much. This code is so much clearer than the code that is in my textbook. Meaningful variable names (rather than, ‘x’, ‘y’, ‘D’, ‘i’, ‘j’. Seriously. The textbook doesn’t declare a single variable as an actual word. They’re all just letters), and good documentation go a long way. Thanks for your help.
2013-01-12 at 9:33
any one have c# code in MST using windows forms
2013-02-27 at 20:19
Thanks
2013-03-07 at 9:18
fuck you code
2013-07-05 at 20:38
Hurrah! At last I got a website from where I know how to in fact obtain valuable
data concerning my study and knowledge.
2013-08-23 at 18:52
Heya i am for the first time here. I came across this board and I find It really
useful & it helped me out a lot. I hope to give something back and help others
like you aided me.
2015-03-16 at 4:50
This is really very helpful for student
2017-04-15 at 11:20
thank u sir
2019-06-20 at 6:59
Thanks for the marvelous posting! I certainly enjoyed reading it, you are a great
author. I will remember to bookmark your blog and will eventually come back at some point.
I want to encourage continue your great work, have a nice
weekend!