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.