Finding the minimum spanning tree (MST)

Question

I have a set of points at which I want to find the minimum spanning tree with PostGIS. I have no lines between them, I only have the starting point from which to start building the tree (the Multilinestring)
I don't know how to start coding this, would it be better to do it with a recursive query? maybe implement the Prim or Kruskal algorithms using the distances between the points?
For now, I have a table with the points (id, geom) and the starting point (start_point: = getStartPoint (points))

MST: minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

liap307 · Accepted Answer

Thanks to @spacedman I was able to solve it, using the code from the following post: gist.github.com/andrewxhill/13de0618d31893cdc4c5
I leave an example for those who need to reproduce it, once the types and functions of the post have been created (I didn't change anything), you can call the main function as follows:
SELECT (minimum_spanning_tree_calc( minimum_spanning_tree(geom ,  id::text ORDER BY id ASC) )).* 
FROM tree_points

Here is a mini dataset to run and see the result:
with tree_points as(
    SELECT row_number() OVER () as id,geom 
    FROM
    unnest(array['POINT(0 0)'::geometry,'POINT(1 1)'::geometry,'POINT(2 2)'::geometry,'POINT(2 3)'::geometry,'POINT(3 3)'::geometry,'POINT(4 3)'::geometry,'POINT(4 4)'::geometry,'POINT(5 3)'::geometry,'POINT(5 5)'::geometry,'POINT(5 6)'::geometry,'POINT(5 7)'::geometry,'POINT(5 8)'::geometry,'POINT(6 6)'::geometry,'POINT(7 7)'::geometry]) as geom
)
SELECT (minimum_spanning_tree_calc( minimum_spanning_tree(geom ,  id::text ORDER BY id ASC) )).* 
FROM tree_points

I hope it was understood, and thanks to spacedman and andrewxhill for your time!

Finding the minimum spanning tree (MST)

One Answer

Add your own answers!

Ask a Question