# Essays/Minimal Spanning Tree

< Essays

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`

- Remove an edge

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.