tree ← wug ##.wmst root ⍝ Minimum Spanning Tree for weighted graph ⍺.
[wmst] uses Prim's algorithm to find a Mimimum Spanning Tree (MST) for weighted,
undirected graph [wug]. An MST is a set of minimum-total-cost edges that conn-
ects all vertices. This set of edges must form a tree; otherwise, it would con-
tain at least one cycle, which means that an edge could be removed, reducing the
total cost without isolating any vertices.
Real-life examples of applications of MSTs include finding lowest-cost ways to
connect computers in a network or the least-expensive bridge-building project to
join up a little cluster of islands.
In the context of undirected graphs, a _tree_ has no concept of hierarchy. There
is no parent-child relationship between the vertices and in particular, there is
no "root" node. A tree is just a graph that contains no cycles.
Tree Non-Tree
└┤ ┌ └┤ ┌
─┼─┼─┤┌ ─┼─┼─┤┌
│└┼┐└┼ │└┼┐└┼
└──── └────┘
However, the representation of a tree used by the graph functions in this work-
space, imposes a hierarchy. A tree is represented by a vector of parent-vertex
indices. Each vertex, apart from the root, which has a dummy index of ¯1, indic-
ates the position in the vector of its parent. This representation is chosen be-
cause it is compact and makes it easy to extract paths from any vertex, back to
the root. Notice that we can produce a "directed" tree from an undirected one
(pictured above left), by selecting _any_ vertex as root. Choosing a root in
this way, immediately imposes a unique hierarchy on the tree: every edge points
from a child vertex back to its parent. Wmst takes this arbitrary root vertex as
right argument.
Technical notes:
Prim's algorithm accumulates the MST as follows:
Starting with the chosen root as a 1-vertex tree,
while there are vertices not connected to the tree,
identify edges connecting these vertices to those within the tree and
incorporate the lowest-cost of these into the tree.
endwhile
Notice that for any graph and root vertex, the MST is _not_ the same as the tree
produced by →wspan←. [wmst] guarantees that the total edge cost is minimised,
while →wspan← produces the lowest cost path from the root to _each_ vertex. The
following weighted, undirected 4-vertex graph illustrates the distinction.
graph MST[A] wspan[A]
A───1───B A─←─1───B A─←─1───B
│ │ ↑ ↑ ↑
2 1 1 2 1
│ │ │ │ │
C───1───D C───1─→─D C D
The difference is that the lowest-cost-path from C to A is C→A, but edge C-A is
too expensive to be included in the MST.
An alternative to Prim's algorithm is Kruskal's algorithm, which builds the MST
by adding edges, rather than vertices. This is an equally good approach, though
it requires a second pass to render the final tree in the format required by the
functions in this workspace.
References:
Kruskal, J.B., On the shortest spanning tree of a graph and the traveling sales-
man problem. Proceedings of the American Mathematical Society, 7:48-50, 1956.
Prim, R.C., Shortest connection networks and some generalizations. Bell Systems
Technology Journal, 36:1389-1401, 1957.
The graph used in the examples below, looks like this:
┌───────A───────┐ Edge Weight
│ │ │ ---- ------
1 3 1 A-B 1
│ │ │ A-C 3
B───2───C───1───D A-D 1
│ │ B-C 2
1 1 C-D 1
│ │ C-E 1
└───────E D-E 1
Examples:
aa ⍝ simple weighted, undirected graph shown above.
┌─────┬───┬───────┬─────┬───┐
│2 3 4│1 3│1 2 4 5│1 3 5│3 4│
├─────┼───┼───────┼─────┼───┤
│1 3 1│1 2│3 2 1 1│1 1 1│1 1│
└─────┴───┴───────┴─────┴───┘
aa wmst 2 ⍝ minimum spanning tree with root 2, c.f.:
2 ¯1 4 1 4
aa wspan 2 ⍝ spanning tree with lowest cost to each vertex.
2 ¯1 2 1 3
See also: wspan span Graphs wGraphs
Back to: contents
Back to: Workspaces