How to connect all points in a graph generated by a set of given vertexes?

This is called the Euclidean minimum spanning tree problem. The Euclidean minimum spanning tree is a subgraph of the Delaunay graph. Exploiting this, we can solve this as follows.

Generate points:

pts = RandomPoint[Disk[], 50]

Compute a Delaunay triangulation and retrieve it as a graph (using IGraph/M, which needs to be installed first):

graph = IGMeshGraph@DelaunayMesh[pts]

enter image description here

Note that this is a weighted graph with the weights representing the edge lengths.

Find a minimum spanning tree (taking edge weights into account) and transfer the vertex coordinates from the original graph.

FindSpanningTree[graph, VertexCoordinates -> GraphEmbedding[graph]]

enter image description here

This gives us the graph (tree) with the shortest total edge length that connects all of the points.

You may find it useful to use

IGSpanningTree[graph, VertexCoordinates -> GraphEmbedding[graph]]

instead, as this function preserves the edge weights (FindSpanningTree throws them away).

Here's a possible alternative for IGraph/M's IGMeshGraph function (so that you don't have to install IGraph/M just for this trivial task):

meshGraph[mesh_] := 
  Graph[
    Range@MeshCellCount[mesh, 0],
    MeshCells[mesh, 1][[All, 1]],
    EdgeWeight -> PropertyValue[{mesh, 1}, MeshCellMeasure],
    VertexCoordinates -> MeshCoordinates[mesh]
  ]

You may be interested in other proximity graph functions that IGraph/M has, such IGLuneBetaSkeleton, IGRelativeNeighborhoodGraph, etc.

Tags:

Graphs And Networks

Trees

Nearest

Recent Posts