KruskalsAlgorithm - Maple Help

GraphTheory

 MinimalSpanningTree
 find least-weight path through graph
 KruskalsAlgorithm
 find least-weight path using Kruskal's algorithm
 PrimsAlgorithm
 find least-weight path using Prim's algorithm

 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

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{with}\left(\mathrm{RandomGraphs}\right):$
 > $A≔\mathrm{Matrix}\left(\left[\left[0,1,0,4,0,0\right],\left[1,0,1,0,4,0\right],\left[0,1,0,3,0,1\right],\left[4,0,3,0,1,0\right],\left[0,4,0,1,0,4\right],\left[0,0,1,0,4,0\right]\right]\right):$
 > $G≔\mathrm{Graph}\left(A\right):$
 > $T≔\mathrm{MinimalSpanningTree}\left(G\right):$
 > $\mathrm{Edges}\left(T,\mathrm{weights}\right)$
 $\left\{\left[\left\{{1}{,}{2}\right\}{,}{1}\right]{,}\left[\left\{{2}{,}{3}\right\}{,}{1}\right]{,}\left[\left\{{3}{,}{4}\right\}{,}{3}\right]{,}\left[\left\{{3}{,}{6}\right\}{,}{1}\right]{,}\left[\left\{{4}{,}{5}\right\}{,}{1}\right]\right\}$ (1)
 > $\mathrm{add}\left(\mathrm{GetEdgeWeight}\left(G,e\right),e=\mathrm{Edges}\left(T\right)\right)$
 ${7}$ (2)
 > $S≔\mathrm{SpanningTree}\left(G\right):$
 > $\mathrm{add}\left(\mathrm{GetEdgeWeight}\left(G,e\right),e=\mathrm{Edges}\left(S\right)\right)$
 ${11}$ (3)
 > $\mathrm{PrimsAlgorithm}\left(G,'w',\mathrm{animate}\right)$

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)
 > $G≔\mathrm{RandomGraph}\left(100,0.5,\mathrm{weights}=0...1.0,\mathrm{connected}\right):$
 > $\mathrm{infolevel}\left[\mathrm{KruskalsAlgorithm}\right]≔4:$
 > $T≔\mathrm{KruskalsAlgorithm}\left(G,'w'\right):$
 KruskalsAlgorithm:   "constructing minimal spanning tree on 100 vertices." KruskalsAlgorithm:   "using Kruskal's algorithm at time 2.175" KruskalsAlgorithm:   "making heap of 2490 edges at time: 2.187" KruskalsAlgorithm:   "finding the edges at time: 2.226" KruskalsAlgorithm:   "exiting Kruskal's algorithm at time 2.258"
 > $w$
 ${2.25620251143321}$ (5)