Essays/Minimal Spanning Tree
< Essays
Jump to navigation
Jump to search
Given a connected, undirected graph with weighted edges, a minimal spanning tree is a subgraph with minimal total weight that connects all the vertices. Kruskal's algorithm finds a minimal spanning tree, as follows:
- Initialize array s of all the edges
- Initialize forest f (a set of trees) where each of n vertices is a separate tree
- While s is nonempty and f has more than one component
- Remove an edge e with minimum weight from s
- If e connects two trees, then combine the two trees with the added edge e
The set of n-1 added edges is a minimum spanning tree.
n mst e implements Kruskal's algorithm. n is the number of vertices; e is a 2-column matrix of the edges sorted by weight. The verb efm produces a 2-column matrix of edges from a weights matrix.
mst=: 4 : 0
z=. 0 2$f=. i.k=.x
for_e. y do.
if. ~:/j=. e{f do.
z=. z,e
if. 1=k=.<:k do. z return. end.
f=. ({.j) (f I.@:= {:j)} f
end.
end.
assert. 0 [ 'graph is not connected'
)
efm=: (($@[ #: I.@]) /: ] # ,@[) _&> ,@:*. <:/~@i.@#
e=: _2 ]\ 1 3 5 6 3 4 3 6 4 6 3 5 2 5 1 4 0 1 2 3 0 2 0 3
7 mst e
0 1
2 5
3 6
5 6
3 4
1 3
m=: ,: _ 23 28 36 _ _ _
m=: m, 23 _ _ 1 20 _ _
m=: m, 28 _ _ 25 _ 17 _
m=: m, 36 1 25 _ 4 16 9
m=: m, _ 20 _ 4 _ _ 15
m=: m, _ _ 17 16 _ _ 3
m=: m, _ _ _ 9 15 3 _
e -: efm m
1
+/ (<"1 ] 7 mst e) { m NB. the cost of the minimal spanning tree
57
See also
Contributed by Roger Hui.0