Minimum Spanning Tree

Overview

The Minimum Spanning Tree (MST) algorithm computes the spanning tree with the minimum sum of edge weights for each connected component in a graph.

The MST has various applications, such as network design, clustering, and optimization problems where minimizing the total cost or weight is important.

Concepts

Spanning Tree

A spanning tree is a connected subgraph that all nodes of a connected graph G= = (V, E) (or a connected component) and forms a tree (i.e., no circles). There may exist multiple spanning trees for a graph, and each spanning tree must have (|V| - 1) edges.

The 11 nodes in the graph below, along with the 10 edges highlighted in red, form a spanning tree of this graph:

Minimum Spanning Tree (MST)

The MST is the spanning tree that has the minimum sum of edge weights. The construction of the MST starts from a given start node. The choice of the start node does not impact the correctness of the MST algorithm, but it can affect the structure of the MST and the order in which edges are added. Different start nodes may result in different MSTs, but all of them will be valid MSTs for the given graph.

After assigning edge weights to the above example, the three possible MSTs with different start nodes are highlighted in red below:

Regarding the selection of start nodes:

• Each connected component requires only one start node. If multiple start nodes are specified, the first one will be considered valid.
• No MST will be computed for connected components that do not have a specified start node.
• Isolated nodes are not considered valid start nodes for computing the MST.

Considerations

• The MST algorithm ignores the direction of edges but calculates them as undirected edges.

Syntax

• Command: algo(mst)
• Parameters:

Examples

The example graph is as below, node A is an electric center, node B~H are the surrounding villages. Each edge is labeled with its UUID and the distance between the connected locations, which represents the required cable length:

File Writeback

UQL
algo(mst).params({
  uuids: [1],
  edge_schema_property: 'distance'
}).write({
  file:{
    filename: 'solution'
    }
})

Results: File solution

File
A--[107]--H
A--[108]--E
E--[111]--G
F--[113]--G
A--[101]--B
A--[104]--D
C--[103]--D

Direct Return

UQL
algo(mst).params({
  ids: 'A',
  edge_schema_property: '@connect.distance'
}) as mst 
return mst

Results: mst

Stream Return

UQL
algo(mst).params({
  uuids: [1],
  edge_schema_property: 'distance'
}).stream() as mst
with pedges(mst) as mstUUID
find().edges(mstUUID) as edges
return sum(edges.distance)

Results: 5.65