Essays/Minimal Spanning Tree

From J Wiki
Jump to: navigation, 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.@#
Mst0.jpg Mst1.jpg
   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.