Prim's MST Algorithm with step-by-step execution Daniel Michel Tavera Student at National Autonomous University of Mexico (UNAM) Mexico e-mail: daniel_michel@ciencias.unam.mx Social 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 optional stepByStep 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}: #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 in V then if a 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, a): 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<e then #if no loop is formed, take the minimum weight edge e:=a: end if: end if: else if a in V and (e={} or a<e)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, e}: H:=H union {e}: E:=E minus {e}: total:= total+e: 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, e, e): 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, a): 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);