Intersections in Kruskal's Minimum spanning tree

Question

I find that some edges of Minimum Spanning Tree (MST) overlap using the union find method detailed here, with modifications - using float instead of integer weights, using integer values instead of string IDs. The grey lines in image below are the MST edges and green / blue edges are shape boundaries.

The edge cost is the euclidean distance between the nodes.

Example showing vertex IDs. Edge weight is added below:

Instead of node 87 -> 138 (weight = 17.7) and 55 -> 134 (weight = 9.49), should it not be 55 -> 138 and 87 -> 134? Is the implementation wrong or can this happen with the algorithm itself?

Please ignore the numbers in brackets besides the vertex numbers (they are the combined weight of edges which connect to each node).

Same example, zoomed out to show other edge weights (removed vertex numbers to remove clutter):

P.S. I found that the distance between 55 -> 138 and 87 -> 134 are exactly the same (12.20656).

Answer 1

Looking at your second image (specifically the unconnected island near the top), it looks like you are pruning your edge list to those that do not cross the shape boundary.

As such, edges 55 <-> 138 and 78 <-> 138 are not available to the Kruskal algorithm and the only edge connecting vertex 138 to the rest of the graph connects to vertex 87.

Answer 2

Answering my own question, based on the questions asked by AakashM.

Specifically, this happened because the edge cost between 55 -> 138 and 87 -> 134 are exactly the same. This happened in my case since I'm generating a shape using an image, hence the distance between points is quantized.

Inspired by this, I added very small random weights (less than the least distance distance between pixels) to the edges which (edit: has not) solved the issue!

So, the algorithm remains good for euclidean MST, and my specific implementation contains a caveat.