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->add_vertex($root); $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 $MST->add_vertex($lw_vertex); $MST->add_weighted_edge($compared_vertex, $lw_vertex, $edge_we +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**

- a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

For: |
Use: |
||

& | & | ||

< | < | ||

> | > | ||

[ | [ | ||

] | ] |