Online Help

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.

$\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\}$

$\mathrm{add}\left(\mathrm{GetEdgeWeight}\left(G\,e\right)\,e=\mathrm{Edges}\left(T\right)\right)$

$7$

$S≔\mathrm{SpanningTree}\left(G\right)\:$

$\mathrm{add}\left(\mathrm{GetEdgeWeight}\left(G\,e\right)\,e=\mathrm{Edges}\left(S\right)\right)$

$11$

$\mathrm{PrimsAlgorithm}\left(G\,'w'\,\mathrm{animate}\right)$

$w$

$7$

$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 1.668"
KruskalsAlgorithm: "making heap of 2490 edges at time: 1.675"
KruskalsAlgorithm: "finding the edges at time: 1.697"
KruskalsAlgorithm: "exiting Kruskal's algorithm at time 1.717"

$w$

$2.25620251143321$