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