find least-weight path through graph
find least-weight path using Kruskal's algorithm
find least-weight path using Prim's algorithm
an undirected graph, weighted or unweighted
(optional) literal animate indicating that an animation of the algorithm should be returned instead of the tree.
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.
A ≔ Matrix⁡0,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:
G ≔ Graph⁡A:
T ≔ MinimalSpanningTree⁡G:
S ≔ SpanningTree⁡G:
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.
G ≔ RandomGraph⁡100,0.5,weights=0.0..1.0,connected:
infolevelKruskalsAlgorithm ≔ 4:
T ≔ KruskalsAlgorithm⁡G,'w':
KruskalsAlgorithm: "constructing minimal spanning tree on 100 vertices."
KruskalsAlgorithm: "using Kruskal's algorithm at time 2.777"
KruskalsAlgorithm: "making heap of 2490 edges at time: 2.785"
KruskalsAlgorithm: "finding the edges at time: 2.814"
KruskalsAlgorithm: "exiting Kruskal's algorithm at time 2.843"
Download Help Document