Options
All
• Public
• Public/Protected
• All

# Module "mst"

## Functions

### Const mst

• mst<T>(edges: T[], maxID: number, cost: Fn<T, number>, verts: Fn<T, [number, number]>): T[]
• Computes the Minimum Spanning Tree from given weighted `edges`, using Kruskal's algorithm.

remarks

Edges can be of any type, but requires unsigned integer vertex IDs. The latter can be extracted via the user supplied `verts` function. The edge weights are extracted via the `cost` function.

The `maxID` arg should equal or greater than the largest vertex ID referenced by the given edges.

The function returns a new array of the original edges, satisfying the MST criteria. The result edges will be in ascending order, based on the supplied cost function.

https://en.wikipedia.org/wiki/Kruskal%27s_algorithm

example
``````// 2D vectors
verts = [[0,0], [0,1], [1,1], [1,2], [4,2]]

// connections (vertex ID pairs)
edges = [[0,1], [0,4], [1,2], [1,3], [2,3], [2,4]]

mst(
edges,
// max vertex ID
4,
// cost function (cartesian distance, from @thi.ng/vectors pkg)
([a,b]) => distSq(verts[a], verts[b]),
// edge vertex IDs
(e) => e
)

// [ [ 0, 1 ], [ 1, 2 ], [ 2, 3 ], [ 2, 4 ] ]``````

#### Parameters

edge pairs

• ##### maxID: number

max vertex ID (+1)

• ##### cost: Fn<T, number>

cost function

• ##### verts: Fn<T, [number, number]>

vertices / graph nodes

#### Returns T[]

Generated using TypeDoc