|
GraphTheory[MinimalSpanningTree]
GraphTheory[KruskalsAlgorithm]
GraphTheory[PrimsAlgorithm]
|
|
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
|
|
|
>
|
|
|
>
|
|
|
>
|
![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]])](/support/helpjp/helpview.aspx?si=6094/file01855/math127.png)
|
|
>
|
|
|
>
|
|
|
>
|
|
|
![{[{1, 2}, 1], [{2, 3}, 1], [{3, 4}, 3], [{3, 6}, 1], [{4, 5}, 1]}](/support/helpjp/helpview.aspx?si=6094/file01855/math142.png)
| (1) |
|
>
|
|
|
| (2) |
|
>
|
|
|
>
|
|
|
| (3) |
|
>
|
|
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.
|
>
|
|
|
| (4) |
|
>
|
|
|
>
|
![infolevel[KruskalsAlgorithm] := 4](/support/helpjp/helpview.aspx?si=6094/file01855/math187.png)
|
|
>
|
|
|
KruskalsAlgorithm: "constructing minimal spanning tree on 100 vertices."
KruskalsAlgorithm: "using Kruskal's algorithm at time 0.251"
KruskalsAlgorithm: "making heap of 2485 edges at time: 0.261"
KruskalsAlgorithm: "finding the edges at time: 0.298"
KruskalsAlgorithm: "exiting Kruskal's algorithm at time 0.343"
| |
|
>
|
|
|
| (5) |
|
|
Download Help Document
Was this information helpful?
