I have been meditating on Prims MST algorithm and a pre-order walk of the MST. The code below is the solution that I generated. The code uses the Graph module for the data structure. There are a couple of assumptions with the solution. 1.)The vertexes have (x,y) coordinates 2.)The weighted edges are the euclidean distance between two edge connected vertices. 3.)The graph is complete and undirected

Let me know what you think and or suggestions for improvement

```#Prims algorithm to calculate MST of \$G
sub prims{
my(\$G, \$root, \$output) = @_;
my \$MST = (ref \$G)->new;
\$MST->set_vertex_attribute(\$root, "X", \$G->get_vertex_attribute(\$r
+oot, "X"));
\$MST->set_vertex_attribute(\$root, "Y", \$G->get_vertex_attribute(\$r
+oot, "Y"));
my @MST;
while(\$MST->vertices != \$G->vertices){
my \$edge_weight = 9**9**9;
my \$lw_vertex;
my \$compared_vertex;
foreach my \$vertex(\$MST->vertices){
foreach my \$successor (\$G->successors(\$vertex)){
##Find the lowest cost safe edge
if((\$edge_weight > \$G->get_edge_weight(\$vertex,\$successor
+)) && ! \$MST->has_vertex(\$successor)){
\$edge_weight = \$G->get_edge_weight(\$vertex,\$successor
+);
\$lw_vertex = \$successor;
\$compared_vertex = \$vertex;
}
}
}
#add the vertex and edge to the cut
+ight);
\$MST->set_vertex_attribute(\$lw_vertex, "X", \$G->get_vertex_att
+ribute(\$lw_vertex, "X"));
\$MST->set_vertex_attribute(\$lw_vertex, "Y", \$G->get_vertex_att
+ribute(\$lw_vertex, "Y"));
push(@MST, "(\$compared_vertex, \$lw_vertex)");
}
##Print out the set for assignment
print  "MST = {@MST} \n";
print {\$output} "MST = {@MST} \n";
return \$MST;
}
```our @preorder_memoized;
sub preorder_tree_walk{
my (\$G, \$root, \$output) = @_;
print "\$root \n";
print {\$output} "\$root \n";
my @edge_vertices;
my \$edge_numb = my @e = \$G->edges_from(\$root);
if(\$edge_numb < 1){return;}

push(@preorder_memoized, \$root);
push(@edge_vertices, \$_->[1]) foreach @e;

#build the tree structure as it would be represented in Euclidean
+ space.
my @sorted_vertices = sort {\$G->get_vertex_attribute(\$a,"X") <=>
+\$G->get_vertex_attribute(\$b,"X") or
\$G->get_vertex_attribute(\$a,"Y") <=>
+\$G->get_vertex_attribute(\$b, "Y") } @edge_vertices;
#print "sorted_ = @sorted_vertices \n";
foreach my \$edge (@sorted_vertices){
if(\$edge ~~ @preorder_memoized){next;}
preorder_tree_walk(\$G, \$edge, \$output);
}
}

In reply to Prims MST Algorithm by b_bot

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

• Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
• Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
• Read Where should I post X? if you're not absolutely sure you're posting in the right place.