Prim's MST Algorithmwith step-by-step executionDaniel Michel Tavera
Student at National Autonomous University of Mexico (UNAM)
Mexico
e-mail: daniel_michel@ciencias.unam.mxSocial service project director: Dr. Patricia Esperanza Balderas Ca\303\261as
Full time professor at National Autonomous University of Mexico (UNAM)
Mexico
e-mail: balderas.patricia@gmail.com
<Text-field style="Heading 1" layout="Heading 1">Introduction</Text-field>
<Text-field style="Text" layout="Normal">Prim's MST Algorithm is a well known solution to the Minimum Spanning Tree (MST) problem, which consists in finding a subset of the edges of a connected weighed graph, such that it satisfies two properties: it maintains connectivity, and the sum of the weights of the edges in the set is minimized.</Text-field>
<Text-field style="Text" layout="Normal"></Text-field>
<Text-field style="Text" layout="Normal">In this work we utilize the definition of Prim's MST algorithm given by Cook et. al. (see References) which is as follows:
</Text-field>
<Text-field style="Text" layout="Normal"> "Keep a tree <Font italic="true">H</Font> = (<Font italic="true">V</Font>(<Font italic="true">H</Font>),<Font italic="true">T</Font>) with <Font italic="true">V</Font>(<Font italic="true">H</Font>) initially {<Font italic="true">r</Font>} for some <Font italic="true">r</Font><Font encoding="UTF-8"> \342\210\210 </Font><Font italic="true">V</Font>, and <Font italic="true">T </Font><Font encoding="UTF-8">initially \342\210\205.</Font></Text-field>
<Text-field style="Text" layout="Normal"> At each step add to <Font italic="true">T</Font> a least-cost edge <Font italic="true">e</Font> not in <Font italic="true">T</Font> such that <Font italic="true">H</Font> remains a tree.
Stop when <Font italic="true">H</Font> is a spanning tree."
</Text-field>
<Text-field style="Text" layout="Normal">This work is part of a social service project consisting in the implementation of several graph theory algorithms with step-by-step execution, intended to be used as a teaching aid in graph theory related courses.</Text-field>
<Text-field style="Text" layout="Normal"></Text-field>
<Text-field style="Text" layout="Normal">The usage examples presented were randomly generated.</Text-field>
<Text-field style="Heading 1" layout="Heading 1">Module usage</Text-field>The PrimMST module contains only a single procedure definition for Prim(G, stepByStep, draw, initial), as follows:Calling Prim(...) will attempt to calculate the MST for graph G using Prim's Algorithm.The parameters taken by procedure Prim(...) are explained below:G is an object of type Graph from Maple's GraphTheory library, it is the graph for which the MST will be computed. Regardless of how it is defined, G will always be treated as though it is undirected. This parameter is not optionalstepByStep is a true/false value. When it is set to true, the procedure will print a message reporting whenever an edge is added to the MST or discarded because it would create a loop. When it is false, only the final result will be shown. This parameter is optional, and its default value is false.draw is a true/false value. When it is set to true, the resulting MST will be displayed after computation finishes; if both stepByStep and draw are true then the graph G will be drawn at every step, highlighting the edges in the MST in green and the discarded edges in red. When draw is set to false, the graphs will not be displayed, and the procedure will only print the total weight of the MST and return the edge list for the MST. This parameter is optional, and its default value is true.initial is a symbol representing the vertex of G from which the algorithm will begin construction of the MST. If the given symbol is not in the vertex list of G, the procedure will terminate reporting an error, otherwise the vertex of G with a label matching the given symbol will be used as initial. This parameter is optional, if no symbol is given, or if {} is passed, the first entry on the vertex list of G will be used.The return value can be one of three possibilities as follows:If draw is true, the procedure returns a graph H such that H is an MST for G.If draw is false, the procedure will return the edge list for H, this is so the value reported by Maple contains more useful information.If initial is a symbol not present in the vertex list of G, or if G is not a connected graph, the procedure will return the string "ERROR".
<Text-field style="Heading 1" layout="Heading 1">Module definition and initialization</Text-field>restart:
with(GraphTheory):
PrimMST := module()
option package;
export Prim;
Prim := proc (G::Graph, stepByStep::truefalse := false, draw::truefalse := true, initial := {})
local H :: list, V :: set, E :: set, e :: list, g::Graph , a::list, discarded::set, initVert::set,total::int, uncheckedVerts::int:
#variable initialization
H:={}: #List of edges of the MST
E:=Edges(G,weights): #backup of G's edge list, used in destructive operations
uncheckedVerts:=nops(Vertices(G))-1: #number of G's vertices not yet reached by the MST
if initial <> {} then #determines initial vertex
if initial in Vertices(G) then
V:={initial}: #user-inputted initial vertex
else
printf("ERROR: initial vertex not in graph");
return "ERROR": #invalid initial vertex
end if:
else
V:={E[1][1][1]}: #default initial vertex
end if:
if draw and stepByStep then
printf("key: yellow = vertices, magenta = initial vertex, blue = original graph edges,\134n\134tgreen = MST edges, red = discarded edges.\134n");
discarded:={}: #discarded edge set, used only when drawing the graph
initVert:=V: #initial vertex backup, used only when drawing the graph
end if:
total:=0: #total weight of the edges in the MST
while nops(E)>0 do; #continue while there are unprocessed edges
e:={}: #assume no edge is added to the MST
for a in E do: #for each edge
if a[1][1] in V then
if a[1][2] in V then
E:=E minus {a}: #if it would cause a loop in the MST, discard the edge
if stepByStep then #report discarded edge if the option is enabled
printf("discarded edge (%a,%a) as it would cause a loop\134n", a[1][1], a[1][2]):
if draw then #draw resulting graph if the option is enabled
discarded:=discarded union {a}:
g:=Graph([op(V)], discarded):
HighlightSubgraph(G, g, red, yellow):
HighlightVertex(G,initVert,magenta):
print(DrawGraph(G));
end if:
end if:
else
if e={} or a[2]<e[2] then #if no loop is formed, take the minimum weight edge
e:=a:
end if:
end if:
else
if a[1][2] in V and (e={} or a[2]<e[2])then
e:=a:
end if:
end if:
end do:
if e<>{} then #if an edge of the MST was found, add it to the MST
V:=V union {e[1][1], e[1][2]}:
H:=H union {e}:
E:=E minus {e}:
total:= total+e[2]:
uncheckedVerts:=uncheckedVerts-1:
if stepByStep then #report added edge if the option is enabled
printf("added edge (%a,%a) with weight %a to the MST\134n", e[1][1], e[1][2], e[2]):
if draw then #draw resulting graph if the option is enabled
g:=Graph([op(V)], H):
HighlightSubgraph(G, g, green, yellow):
HighlightVertex(G,initVert,magenta):
print(DrawGraph(G));
end if:
end if:
if uncheckedVerts=0 then #algorithm ends when all vertices are in the MST
if stepByStep then #report end of computation if the option is enabled
printf("Finished MST construction.\134n"):
break:
end if:
end if:
else
if(E<>{})then #if there are unprocessed edges, but none of them belongs to the MST, report an error
printf("ERROR: unable to construct MST, graph may be disconnected");
return "ERROR":
end if:
end if:
end do:
if (draw) then #print MST if the option is enabled
g:=Graph([op(V)],H):
if stepByStep then
printf("graph for the obtained MST:\134n", a[1][1], a[1][2]):
end if:
print(DrawGraph(g));
printf("total weight of the MST: %a\134n",total): #report total MST weight
return g: #return graph for the MST
else
printf("total weight of the MST: %a\134n",total): #report total MST weight
return H; #return list of edges for the MST
end if:
end proc:
end module:
with (PrimMST);
<Text-field style="Heading 1" layout="Heading 1">Usage examples</Text-field>
<Text-field style="Heading 2" layout="Heading 2">Default Behavior: print resulting MST, without step-by-step reports.</Text-field>vertices:=["a","b","c","d"]:
edges:={[{"a", "b"}, 1],[{"a", "c"}, 3],[{"b", "c"}, 2],[{"b", "d"}, 5],[{"c", "d"}, 9]}:
g := Graph(vertices,edges):
Prim(g);
<Text-field style="Heading 2" layout="Heading 2">Shows step-by-step reports, but doesn't print the MST</Text-field>vertices:=[1,2,3,4,5,6]:
edges:={[{1,2},6],[{1,3},2],[{1,4},5],[{2,3},6],[{2,4},4],[{2,5},5],[{3,4},6],[{3,5},3],[{3,6},2],[{4,5},6],[{5,6},2]}:
g := Graph(vertices,edges):
Prim(g,true,false);
<Text-field style="Heading 2" layout="Heading 2">Shows step-by-step process with graphs for each step, using initial vertex "e"</Text-field>vertices:=["a","b","c","d","e"]:
edges:={[{"a","b"},3],[{"a","c"},2],[{"a","d"},2],[{"b","c"},5],[{"b","d"},2],[{"b","e"},4],[{"c","e"},1],[{"d","e"},7]}:
g := Graph(vertices,edges):
Prim(g,true,"e");
<Text-field style="Heading 1" layout="Heading 1">References</Text-field>Cook, William J. et. al. Combinatorial Optimization. Wiley-Interscience, 1998. ISBN 0-471-55894-XLegal Notice: \302\251 2016. Maplesoft and Maple are trademarks of Waterloo Maple Inc. Neither Maplesoft nor the authors are responsible for any errors contained within and are not liable for any damages resulting from the use of this material. This application is intended for non-commercial, non-profit use only. Contact the authors for permission if you wish to use this application in for-profit activities.