Finding the minimum spanning tree in a Neo4j graph

The procedure to find the minimum spanning tree in the GDS plugin is as follows:

MATCH (A:Node {name: "A"})
CALL gds.alpha.spanningTree.minimum.write("graph_weighted", {
    startNodeId: id(A),
    relationshipWeightProperty: 'weight',
    writeProperty: 'MINST',
    weightWriteProperty: 'writeCost'
})
YIELD createMillis, computeMillis, writeMillis, effectiveNodeCount
RETURN *

This will actually create new relationships for each edge in the minimum spanning tree. To retrieve these edges, you can use the following:

MATCH (n)-[r:MST]-(m)
RETURN n, r, m

This query produces the following output, consistent with the result we obtained earlier by running Prim's algorithm:

 

Note that you can also find the maximum spanning tree and the k-spanning tree to find a spanning tree using only k nodes.