In this section we give a short description of an step
algorithm for solving the minimum-cost spanning tree problem on an mesh-connected computer. We assume that the diagonal
element in each mesh row can broadcast a value to the other elements
of the row in a single step. This type of broadcast can be simulated
by a mesh without this capability by slowing the algorithm down by a
constant factor
[8, 9, 10].
The algorithm proceeds as follows. We assume that the input graph is
given in the form of a matrix of edge costs which enters
row-by-row through the top of the mesh. Matrix row *i* is modified as
it passes over rows *1* through *i-1* and is stored when it reaches
mesh row *i*. When matrix row *i* passes over mesh row *k*, the value
is broadcast right and left from the diagonal cell
. Each cell knows the value of
and computes

which is passed down to the
next mesh row. After reaching mesh row *i*, matrix row *i* stays
there until each matrix row *l*, , above it has
passed over it and then continues to propagate down, passing over the
rest of the matrix rows. The output matrix exits row-by-row
from the bottom of the mesh. By theorem 1, the adjacency matrix of
the minimum-cost spanning tree can be constructed by comparing the
input and output matrices.

Sun Jul 21 23:35:52 EDT 1996