ngraph.kruskal

1.1.0 • Public • Published

ngraph.kruskal build status

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

Package Sidebar

Install

npm i ngraph.kruskal

Weekly Downloads

4

Version

1.1.0

License

MIT

Unpacked Size

245 kB

Total Files

10

Last publish

Collaborators

  • anvaka