GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GraphTheory/MinimalSpanningTree

GraphTheory

  

MinimalSpanningTree

  

KruskalsAlgorithm

  

PrimsAlgorithm

 

Calling Sequence

Parameters

Description

Examples

Calling Sequence

MinimalSpanningTree(G)

MinimalSpanningTree(G,w,animate)

KruskalsAlgorithm(G,w,animate)

PrimsAlgorithm(G,w,animate)

Parameters

G

-

an undirected graph, weighted or unweighted

w

-

(optional) name

animate

-

(optional) literal animate indicating that an animation of the algorithm should be returned instead of the tree.

Description

• 

MinimalSpanningTree, KruskalsAlgorithm, and PrimsAlgorithm all return a spanning tree of the undirected graph G with minimum possible weight. If the graph G is unweighted, each edge is considered to have weight 1.

• 

If the optional parameter w is given, it is assigned the weight of the minimal spanning tree.

• 

If the literal animate, or animate=true is given, an animation of the application of the algorithm will be returned instead of the minimal spanning tree.

• 

The routine PrimsAlgorithm uses Prim's algorithm for computing the minimal spanning tree and the routine KruskalsAlgorithm uses Kruskal's algorithm. The routine MinimalSpanningTree uses Kruskal's algorithm.

• 

Setting infolevel[KruskalsAlgorithm] := 4; and infolevel[PrimsAlgorithm] := 4; results in some information being printed out, indicating the steps of the respective algorithms.

Examples

withGraphTheory:

withRandomGraphs:

AMatrix0,1,0,4,0,0,1,0,1,0,4,0,0,1,0,3,0,1,4,0,3,0,1,0,0,4,0,1,0,4,0,0,1,0,4,0:

GGraphA:

TMinimalSpanningTreeG:

EdgesT,weights

1,2,1,2,3,1,3,4,3,3,6,1,4,5,1

(1)

addGetEdgeWeightG,e,e=EdgesT

7

(2)

SSpanningTreeG:

addGetEdgeWeightG,e,e=EdgesS

11

(3)

PrimsAlgorithmG,w,animate

Note: To animate the example above, open this help page as a worksheet, click the plot in the worksheet, and use the controls in the animation toolbar above the worksheet.

w

7

(4)

GRandomGraph100,0.5,weights=0...1.0,connected:

infolevelKruskalsAlgorithm4:

TKruskalsAlgorithmG,w:

KruskalsAlgorithm:   "constructing minimal spanning tree on 100 vertices."
KruskalsAlgorithm:   "using Kruskal's algorithm at time 1.579"
KruskalsAlgorithm:   "making heap of 2507 edges at time: 1.588"
KruskalsAlgorithm:   "finding the edges at time: 1.608"
KruskalsAlgorithm:   "exiting Kruskal's algorithm at time 1.639"

w

2.23695111523435

(5)

See Also

AllPairsDistance

Diameter

SpanningTree

WeightMatrix