# Essays/Minimal Spanning Tree

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
```