A minimum-spanning-tree algorithm for ngraph.graph
npm install ngraph.kruskalA minimum-spanning-tree algorithm for ngraph.graph.
Runtime: O(E log E), where E is number of edges in the graph.
`` js
var kruskal = require('ngraph.kruskal');
// graph is an instance of ngraph.graph
var tree = kruskal(graph);
// Tree is array of edges that constitute minimum spanning tree (MSP).
assert(Array.isArray(tree));
// Each edge of the MSP is an edge of the graph:
var treeEdge = tree[0];
assert(
graph.getLink(treeEdge.fromId, treeEdge.toId)
);
`
Note: This algorithm finds all trees, even in the graph with disconnected
components.
`
npm install ngraph.kruskal
MIT