{"id":21,"date":"2011-08-24T20:49:37","date_gmt":"2011-08-24T20:49:37","guid":{"rendered":"http:\/\/learninglover.com\/blog\/?p=21"},"modified":"2013-11-06T20:19:29","modified_gmt":"2013-11-07T01:19:29","slug":"prims-algorithm","status":"publish","type":"post","link":"https:\/\/learninglover.com\/blog\/index.php\/2011\/08\/24\/prims-algorithm\/","title":{"rendered":"Prim’s Algorithm"},"content":{"rendered":"

I have just written a script that executes Prim’s Algorithm<\/a> that finds the minimum spanning tree on a randomly generated graph.<\/p>\n

Given a weighted graph, many times we are interested in finding a minimum spanning tree (MST) for that graph. This has many applications including the very important network simplex method. Prim’s algorithm is a greedy method which does finds this MST. A spanning tree is a subset of the edges of a graph that connects every vertex, but contains no cycles. This spanning tree is called a minimum spanning tree if in addition the sum of the weights of the edges included in this tree is less than or equal to the sum of the weights of the edges of any other spanning tree for this graph.<\/p>\n

Prim’s algorithm works by the following procedure.
\n1. Let Treev<\/sub><\/em> be the set of vertices included in the tree, and TreeE<\/sub><\/em> be the set of edges included in the tree. Initially Treev<\/sub><\/em> and TreeE<\/sub><\/em> are empty.
\n2. Add an arbitrary vertex to Treev<\/sub><\/em> (TreeE<\/sub><\/em> is still empty).
\n3. Find the edge e<\/em> of minimum weight such that one vertex is in Treev<\/sub><\/em> and vertex is not in Treev<\/sub><\/em>. Add the associated vertex to Treev<\/sub><\/em>, and add e<\/em> to TreeE<\/sub><\/em>.
\n4. If edge was found in step 3, goto 5, else go to 6.
\n5. If the number of vertices in Treev<\/sub><\/em> is less than the number of vertices in the original graph, then the graph is not connected and thus does not contain a minimum spanning tree. Goto 8.
\n6 If the number of vertices in Treev<\/sub><\/em> is less than the number of vertices in the original graph, go to 2, else go to 7.
\n7. Output “The Minimum Spanning Tree is “, TreeE<\/sub><\/em>.
\n8. Output “This graph does not have a minimum spanning tree because it is not connected. ”<\/p>\n

For example, consider the graph represented by the following adjacency matrix:<\/p>\n\n\n\n\n\n\n\n
<\/td>\n0<\/td>\n1<\/td>\n2<\/td>\n3<\/td>\n4<\/td>\n<\/tr>\n
0<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n13<\/td>\n12<\/td>\n<\/tr>\n
1<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n16<\/td>\n<\/tr>\n
2<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n24<\/td>\n<\/tr>\n
3<\/td>\n13<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n13<\/td>\n<\/tr>\n
4<\/td>\n12<\/td>\n16<\/td>\n24<\/td>\n13<\/td>\n–<\/td>\n<\/tr>\n<\/table>\n

\"Graph<\/p>\n

Initially our tree (Tv<\/sub> is empty). The first step says to choose a random vertex and add it to the tree, so lets choose vertex 2. <\/p>\n

Iteration 1: Now our tree contains the vertex 2 (i.e. Tv<\/sub> = {2}) and likewise TE<\/sub> contains the edges coming from Tv<\/sub>. Thus TE<\/sub> = {(2, 4)}.
\nWe want to choose the cheapest edge that has one endpoint in Tv<\/sub> and one endpoint not in Tv<\/sub>. These edges are represented by TE<\/sub>. Notice that TE<\/sub> only contains one edge, so we select this
\nedge, which has a cost of 24. <\/p>\n

Iteration 2: Our tree thus contains the vertices 2 and 4 (i.e Tv<\/sub> = {2, 4}) and likewise TE<\/sub> contains the edges coming from Tv<\/sub>. Thus TE<\/sub> = {(0, 4), (1, 4), (3, 4)}.
\nAgain, we want to choose the cheapest edge that has one endpoint in Tv<\/sub> and one endpoint not in Tv<\/sub>. This will be the edge (0, 4) which has a cost of 12. <\/p>\n

Iteration 3: Now Tv<\/sub> = {0, 2, 4} and TE<\/sub> = {(1, 4), (3, 4), (0, 3)}. The cheapest of these three edges is the edge (0, 3) with a cost of 13, which means we will add it to our tree. <\/p>\n

Iteration 4: Now Tv<\/sub> = {0, 2, 3, 4} and TE<\/sub> = {(1, 4)}. Since (1, 4) is the only edge connected to our tree we add it and it has a cost of 16. <\/p>\n

Iteration 5: Now Tv<\/sub> = {0, 1, 2, 3, 4} and TE<\/sub> = {}. Because our tree contains all the vertices of the graph it is now spanning tree. The cost of this spanning tree is 24 + 12 + 13 + 16 = 65. <\/p>\n

To learn more and see more examples, view Prim’s Algorithm at LEARNINGlover.com<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

I have just written a script that executes Prim’s Algorithm that finds the minimum spanning tree on a randomly generated graph. Given a weighted graph, many times we are interested in finding a minimum spanning tree (MST) for that graph. This has many applications including the very important network simplex method. Prim’s algorithm is a […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-21","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/posts\/21","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=21"}],"version-history":[{"count":0,"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/posts\/21\/revisions"}],"wp:attachment":[{"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=21"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=21"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=21"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}