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); } }

Comment on Prims MST Algorithm
Select or Download Code
Re: Prims MST Algorithm
by educated_foo (Vicar) on Apr 22, 2013 at 17:20 UTC
    If it works, use it. However, Prim's algorithm is O(E), so in a complete graph you will get worst-case performance. If you have a complete graph and Euclidean distances, I suspect you can do much better using some geometric algorithm, perhaps by sorting the vertices in one dimension and using a sweep-line algorithm.
    Just another Perler interested in Algol Programming.
Re: Prims MST Algorithm
by Old_Gray_Bear (Bishop) on Apr 22, 2013 at 18:40 UTC
    A note for the Mathematically Forgetful -- MST == Minimum Spanning Tree. (See Prims Algorithm).

    .oO(It's been a loooong time....)

    ----
    I Go Back to Sleep, Now.

    OGB