snorkel's blog

Column-wise MST in grid.
By snorkel, history, 4 years ago, In English

Please help me find the solution to this problem, which basically asks to find MST in grid which goes to all the columns from left to right. We can go to the adjacent cell in the grid (no diagonals).

There can be other solutions but I'm looking for one with Kruskal's or Prim's algorithm. Note that MST always has maximum weight edge as small as possible.

Thanks.

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Not sure if you can call it MST, but there is Kruskal-like solution. Sort all cells by increasing weight. Iterate over all cells and maintain DSU. When you encounter a cell, check all neighbours and unite your cell with a neighbor, iff it was checked earlier (if it's weight is less or equal than current one). Additionally, when your cell is in the first column or in the last column, unite it with a corresponding additional vertex (make two of them: one for the first column and one for the last). Stop when two additional vertices become connected.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks for the nice solution!

    By the way, it is much less intuitive for me than binary search + connectivity check. But your solution is I think what I was looking for.

    And about MST, As I know in MST maximum edge weight is minimized, btw just maximum edge weight minimized spanning tree does not have to be MST. So I think MST would be the solution for this problem, but I was not able to construct/implement it for some reasons.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

The problem effectively asks you to minimize the maximum vertex weight on a path from the left column to the right column in some vertex-weighted grid graph. To reduce this to MST, you need* to choose edge weights so that the max edge weight on a path is equal to the max vertex weight on the same path. One easy choice that works is to set each edge weight equal to the max of the weights of its two incident vertices.

*This could also be done with/on some auxiliary graph, for example by replacing each vertex in the original graph with a star. But the options for so doing seem needlessly complex.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I reduced it like this: added full of zero column to the left and created edges, the weights were equal to the weight of the vertex from which I discovered the edge. I think here is the mistake.

    Your way is very nice and I will use it in the future.

    Thanks.

    → Reply