The first known algorithm for finding a minimum spanning tree was developed by the Czech scientist Otakar Borůvka in 1926, while trying to find an efficient electricity network for Moravia. Prim’s algorithm was invented by Jarnik in 1930 and rediscovered by Prim in 1957. It is similar to Dijkstra’s shortest path algorithm but, rather than minimizing the total length of a path ending at each relationship, it minimizes the length of each relationship individually. Unlike Dijkstra’s, Prim’s can tolerate negative-weight relationships.

The algorithm operates as follows:

The MST algorithm only gives meaningful results when run on a graph, where the relationships have different weights. If the graph has no weights, or all relationships have the same weight, then any spanning tree is a minimum spanning tree.

The following will run the algorithm and write back results: 

CALL gds.alpha.spanningTree.write(configuration: Map)
YIELD createMillis, computeMillis, writeMillis, effectiveNodeCount

The following will compute the minimum weight spanning tree and write the results: 

CALL gds.alpha.spanningTree.minimum.write(configuration: Map)
YIELD createMillis, computeMillis, writeMillis, effectiveNodeCount

The following will compute the maximum weight spanning tree and write the results: 

CALL gds.alpha.spanningTree.maximum.write(configuration: Map)
YIELD createMillis, computeMillis, writeMillis, effectiveNodeCount

The following will run the k-spanning tree algorithms and write back results: 

CALL gds.alpha.spanningTree.kmin.write(configuration: Map)
YIELD createMillis, computeMillis, writeMillis, effectiveNodeCount

CALL gds.alpha.spanningTree.kmax.write(configuration: Map)
YIELD createMillis, computeMillis, writeMillis, effectiveNodeCount

The following will create a sample graph: 

CREATE (a:Place {id: 'A'}),
       (b:Place {id: 'B'}),
       (c:Place {id: 'C'}),
       (d:Place {id: 'D'}),
       (e:Place {id: 'E'}),
       (f:Place {id: 'F'}),
       (g:Place {id: 'G'}),
       (d)-[:LINK {cost:4}]->(b),
       (d)-[:LINK {cost:6}]->(e),
       (b)-[:LINK {cost:1}]->(a),
       (b)-[:LINK {cost:3}]->(c),
       (a)-[:LINK {cost:2}]->(c),
       (c)-[:LINK {cost:5}]->(e),
       (f)-[:LINK {cost:1}]->(g);

Minimum weight spanning tree visits all nodes that are in the same connected component as the starting node, and returns a spanning tree of all nodes in the component where the total weight of the relationships is minimized.

The following will run the Minimum Weight Spanning Tree algorithm and write back results: 

MATCH (n:Place {id: 'D'})
CALL gds.alpha.spanningTree.minimum.write({
  nodeProjection: 'Place',
  relationshipProjection: {
    LINK: {
      type: 'LINK',
      properties: 'cost',
      orientation: 'UNDIRECTED'
    }
  },
  startNodeId: id(n),
  relationshipWeightProperty: 'cost',
  writeProperty: 'MINST',
  weightWriteProperty: 'writeCost'
})
YIELD createMillis, computeMillis, writeMillis, effectiveNodeCount
RETURN createMillis, computeMillis, writeMillis, effectiveNodeCount;

To find all pairs of nodes included in our minimum spanning tree, run the following query: 

MATCH path = (n:Place {id: 'D'})-[:MINST*]-()
WITH relationships(path) AS rels
UNWIND rels AS rel
WITH DISTINCT rel AS rel
RETURN startNode(rel).id AS source, endNode(rel).id AS destination, rel.writeCost AS cost

Figure 6.1. Results

The minimum spanning tree excludes the relationship with cost 6 from D to E, and the one with cost 3 from B to C. Nodes F and G aren’t included because they’re unreachable from D.

Maximum weighted tree spanning algorithm is similar to the minimum one, except that it returns a spanning tree of all nodes in the component where the total weight of the relationships is maximized.

The following will run the maximum weight spanning tree algorithm and write back results: 

MATCH (n:Place{id: 'D'})
CALL gds.alpha.spanningTree.maximum.write({
  nodeProjection: 'Place',
  relationshipProjection: {
    LINK: {
      type: 'LINK',
      properties: 'cost'
    }
  },
  startNodeId: id(n),
  relationshipWeightProperty: 'cost',
  writeProperty: 'MAXST',
  weightWriteProperty: 'writeCost'
})
YIELD createMillis, computeMillis, writeMillis, effectiveNodeCount
RETURN createMillis,computeMillis, writeMillis, effectiveNodeCount;

Figure 6.2. Results

MATCH (n:Place{id: 'D'})
CALL gds.alpha.spanningTree.kmin.write({
  nodeProjection: 'Place',
  relationshipProjection: {
    LINK: {
      type: 'LINK',
      properties: 'cost'
    }
  },
  k: 3,
  startNodeId: id(n),
  relationshipWeightProperty: 'cost',
  writeProperty:'kminst'
})
YIELD createMillis, computeMillis, writeMillis, effectiveNodeCount
RETURN createMillis,computeMillis,writeMillis, effectiveNodeCount;

MATCH (n:Place)
WITH n.id AS Place, n.kminst AS Partition, count(*) AS count
WHERE count = 3
RETURN Place, Partition

MATCH (n:Place{id: 'D'})
CALL gds.alpha.spanningTree.kmax.write({
  nodeProjection: 'Place',
  relationshipProjection: {
    LINK: {
      type: 'LINK',
      properties: 'cost'
    }
  },
  k: 3,
  startNodeId: id(n),
  relationshipWeightProperty: 'cost',
  writeProperty:'kmaxst'
})
YIELD createMillis, computeMillis, writeMillis, effectiveNodeCount
RETURN createMillis,computeMillis,writeMillis, effectiveNodeCount;

MATCH (n:Place)
WITH n.id AS Place, n.kmaxst AS Partition, count(*) AS count
WHERE count = 3
RETURN Place, Partition