1
$\begingroup$

I have a particular grid with weighted edges connecting each vertex:

grid

From this I'm looking for an easy method to obtain a Minimum Spanning Tree.

I can easily check columns or rows and remove all but the lowest weight, but this will only provide me with a regular spanning tree instead of the desired MST. Columns, for example:

columns

I do know I can use the various classic algorithms such as Kruskal's, Prim's, or Boruvka's, but I'm wondering if there's an easier method for grids specifically since it was easy enough to get a regular tree (and if the easiest method happens to be one of the classic algorithms, which might be the best suited for grids).

$\endgroup$
  • $\begingroup$ You have just this particular grid, or is this an example of a more general construction? If the latter, what is the pattern for the edge weights? $\endgroup$ – Casteels Jun 28 '15 at 10:26
  • $\begingroup$ It's a general construction. The edge weights are just assigned randomly. $\endgroup$ – Matthew Jun 28 '15 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.