Differences between revisions 19 and 20
 ⇤ ← Revision 19 as of 2007-09-05 21:26:05 → Size: 1848 Editor: RogerHui Comment: ← Revision 20 as of 2008-12-08 10:45:38 → ⇥ Size: 1840 Editor: anonymous Comment: converted to 1.6 markup Deletions are marked like this. Additions are marked like this. Line 37: Line 37: || attachment:mst0.jpg || attachment:mst1.jpg || || {{attachment:mst0.jpg}} || {{attachment:mst1.jpg}} || Line 65: Line 65: [[BR]] <
> Line 68: Line 68: * [http://en.wikipedia.org/wiki/Minimal_spanning_tree Wikipedia] * [:Essays/Dendrite] * [[WikiPedia:Minimal_spanning_tree|Wikipedia]] * [[Essays/Dendrite]] Line 71: Line 71: [[BR]] <
>

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