@saehrimnir/druidjs / minimum_spanning_tree
Function: minimum_spanning_tree()
ts
function minimum_spanning_tree(edges: WeightedEdge[], N: number): WeightedEdge[];Defined in: util/minimum_spanning_tree.js:25
Computes a minimum spanning tree of a weighted graph with Kruskal's algorithm.
The graph is given as an edge list over vertices 0 … N-1, so a caller holding a sparse structure (a k-nearest-neighbor graph, say) never has to materialize the N ⨯ N matrix. Edges are treated as undirected; passing both [u, v, w] and [v, u, w] is harmless, the second one is skipped as a cycle.
If the graph is disconnected the result is a minimum spanning forest — one tree per connected component, and fewer than N - 1 edges. Callers that need a connected result must guarantee a connected input.
Parameters
| Parameter | Type | Description |
|---|---|---|
edges | WeightedEdge[] | The edges of the graph. Not mutated. |
N | number | The number of vertices. Vertex indices must be in [0, N). |
Returns
WeightedEdge[]
The edges of the minimum spanning tree, ascending by weight.