Awesome
ngraph.kruskal
A minimum-spanning-tree algorithm for ngraph.graph.
Runtime: O(E log E)
, where E
is number of edges in the graph.
usage
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.
install
npm install ngraph.kruskal
License
MIT