최소 스패닝 트리 (MST) 찾기

Question

PostGIS로 최소 스패닝 트리를 찾고자하는 지점이 있습니다. 나는 그들 사이에 선이 없으며, 트리 구축을 시작할 시작점 (Multilinestring) 만 있습니다.

코딩을 시작하는 방법을 모르겠습니다. 재귀 쿼리를 사용하는 것이 더 낫습니까? 점 사이의 거리를 사용하여 Prim 또는 Kruskal 알고리즘을 구현할 수 있습니까?

지금은 점 (id, geom)과 시작점 ( start_point: = getStartPoint (points)) 이있는 테이블이 있습니다.

MST : 최소 가중치 스패닝 트리는 모든 정점을 함께 연결하고 가능한 최소 총 가장자리 가중치로 모든 정점을 연결하는 연결된 가장자리 가중치 무 방향 그래프 가장자리의 하위 집합입니다.

Answer 1

@spacedman 덕분에 다음 게시물의 코드를 사용하여 해결할 수있었습니다. gist.github.com/andrewxhill/13de0618d31893cdc4c5

재현 할 필요가있는 사람들을 위해 예제를 남겨두고 게시물의 유형과 기능이 생성되면 (아무것도 변경하지 않았습니다) 다음과 같이 main 함수를 호출 할 수 있습니다.

SELECT (minimum_spanning_tree_calc( minimum_spanning_tree(geom ,  id::text ORDER BY id ASC) )).* 
FROM tree_points 

다음은 실행하고 결과를 볼 수있는 미니 데이터 세트입니다.

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 

이해가 되셨기를 바라며 시간을 내주신 spacedman과 andrewxhill에게 감사드립니다!