A Maple Package implementing
Kruskal's Algorithms for Finding a Minimum Spanning Tree
(for a connected and weighted graph) 

Jay Pedersen
University of Nebraska at Omaha Student
E-mail: jayped007@gmail.com 

Code Version 1.0, Date 2007-07-10, Maple Version 11

Project: Implement Kruskal's Algorithm for determining a minimum-cost spanning tree for a connected and weighted graph. 

Please report any errors to Jay Pedersen at emaile jaypd007@gmail.com.
 

References 

Kruskal's Minimum Spanning Tree algorithm is a well-known algorithm.  One place where it is 

defined is in  'Algorithms Sequential and Parallel' by Russ Miller and Laurence Boxer, page 331 

(c) 2005, ISBN 1-58450-412-9. 

 

Maple programming is described in "maple 9; Introductory Programming Guide" 

from Maplesoft; ISBN 189451143-3.  This is also available from the maplesoft website. 

 

Input Format (for Network definition) 

The algorithm takes as input a list containing a network definition. 

 

The list contains edge definitions for the network; with 3 values in each. 

The first 2 values define the nodes (vertices) for the edge and the 3rd value is 

the cost for traveling across the edge. 

 

For example; the following definition defines a network with 4 nodes (vertices) 

and 6 edges (arcs, connections). 

 

net := [ 

[1, 2, 1], 

[1, 3, 3], 

[2, 3, 2], 

[3, 2, 4], 

[2, 4, 5], 

[3, 4, 9] 

]; 

Algorithm Code 

 

>

Kruskals_MST := module()  option package;  export Kruskals_Algorithm;  Kruskals_Algorithm := proc (network_def::list, make_graph::truefalse)    local edgelist :: list, edge :: list, cmp_weights, mst :: set,          mst_edges :: posint, i :: posint, vertices :: set, vertex,          vertex_count :: posint, C :: table, rep_target, rep_value, G,          tot_cost :: posint;    # Obtain list of edges sorted by weight    cmp_weights := proc(a,b) return ( is(a[3] < b[3]) ) end proc:    edgelist := sort(network_def, cmp_weights);    # Obtain list of vertices    vertices := {}:    for edge in edgelist do vertices := vertices union { edge[1], edge[2] } end do:    vertex_count := nops(vertices);    mst_edges := vertex_count - 1; # number of edges in MST = vertices - 1    # Initialize cycle-detecting table    C := table;    for vertex in vertices do C[vertex] := vertex end do;    # printf("vertex_count = %d, edges = %d\n", vertex_count, nops(edgelist));    # Generate MST    mst := {};    for i to nops(edgelist) while (nops(mst) < mst_edges) do;        edge := edgelist[i]:        if (C[edge[1]] <> C[edge[2]]) then            mst := mst union { edge };            rep_target := C[edge[2]];            rep_value  := C[edge[1]];            for vertex in vertices do;                if (C[vertex]=rep_target) then                    C[vertex] := rep_value                end if;            end do;        end if;    end do:    # Sanity check    if (nops(mst) <> mst_edges) then        printf("*** Did not construct MST, %d <> %d ***\n",             nops(mst), mst_edges);        printf("*** Error in input? Not connected graph? ***\n");        return;    end if;    # At this point, shortest paths for graph is determined.    printf("\nMinimum Spanning Tree:\n\n");    tot_cost := 0;    for edge in mst do;        printf ("%A - %A (%d)\n", edge[1], edge[2], edge[3]);        tot_cost := tot_cost + edge[3];    end;    printf("Total cost = %d\n", tot_cost);    printf("\n");    # create graph G if requested    if (make_graph) then        new(G):        addvertex([seq(vertices[i],i=1..nops(vertices))],G);        for edge in mst do connect({edge[1]},{edge[2]},G) end do;        return(draw(G));    end if;    return mst;  end proc: # Kruskals_Algorithm end module: # Kruskals_MST with(Kruskals_MST);

 

 

Example Usage 

Usage: The routine Kruskals_Algorithm is invoked to determine a minimum spanning tree 

paths from the source node to destination nodes on the network that it is given. 

Syntax: Kruskals_Algorithm(network, display_graph);

Arguments:
Network - list defining the network (see "Input Format" section).
display_graph - true/false, if true => graphically display min spanning tree
 

>	net := [ [1, 2, 1], # arc 1 - from 1 to 2, cost=1 [1, 3, 3],[2, 3, 2],[3, 2, 4],[2, 4, 5],[3, 4, 9] ]: Kruskals_Algorithm(net, false); # dont display graph

 

 

Minimum Spanning Tree: 1 - 2 (1) 2 - 3 (2) 2 - 4 (5) Total cost = 8

 

>

# More complex network, show resulting graph net := [ [1,2,5],  # arc from 1 to 2, cost 5 [1,3,9],[1,4,20],[1,5,4],[1,8,14],[1,9,15], [2,1,5],[2,3,6],[3,1,9],[3,2,6],[3,4,15], [3,5,10],[4,1,20],[4,3,15],[4,5,20],[4,6,7], [4,7,12],[5,1,4],[5,3,10],[5,4,20],[5,6,3], [5,7,5],[5,8,13],[5,9,6],[6,4,7],[6,5,3], [7,4,12],[7,5,5],[7,8,7],[8,1,14],[8,5,13], [8,7,7],[8,9,5],[9,1,15],[9,5,6],[9,8,5] ]: Kruskals_Algorithm(net, true);

 

 

Minimum Spanning Tree: 2 - 1 (5) 3 - 2 (6) 5 - 1 (4) 6 - 4 (7) 6 - 5 (3) 7 - 5 (5) 9 - 5 (6) 9 - 8 (5) Total cost = 41

 

>

# Network with city name labels net := [["Omaha","Chicago",5],        ["Omaha","St Louis",6],        ["St Louis","Chicago",5],        ["St Louis","Cincinatti",6],        ["Chicago","Boston",11],        ["Chicago","New York",9],        ["Chicago","Pittsburgh",7],        ["Chicago","Cincinatti",5],        ["Chicago","Memphis",6],        ["Boston","New York",3],        ["New York","Pittsburgh",5],        ["New York","Washington DC",5],        ["Pittsburgh","Washington DC",5],        ["Pittsburgh","Atlanta",7],        ["Pittsburgh","Cincinatti",4],        ["Washington DC","Cincinatti",6],        ["Washington DC","Atlanta",4],        ["Washington DC","Miami",8],        ["Cincinatti","Atlanta",6],        ["Cincinatti","Memphis",6],        ["Memphis","Atlanta",7],        ["Memphis","New Orleans",4],        ["New Orleans","Atlanta",6],        ["Atlanta","Miami",6]]: Kruskals_Algorithm(net,true);

 

 

Minimum Spanning Tree: Omaha - Chicago (5) St Louis - Chicago (5) Chicago - Cincinatti (5) Boston - New York (3) New York - Washington DC (5) Pittsburgh - Washington DC (5) Pittsburgh - Cincinatti (4) Washington DC - Atlanta (4) Memphis - New Orleans (4) New Orleans - Atlanta (6) Atlanta - Miami (6) Total cost = 52

 

Legal Notice: The copyright for this application is owned by the author(s). Neither Maplesoft nor the author 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 author for permission if you wish to use this application in for-profit activities.