breadth-first

Breadth-first search for directed graphs.

Install

$ npm install breadth-first

Usage

We want to traverse the following graph.

import bfs from "breadth-first";

// First, we define our edges.
const edges = [
  ["put on your shoes", "tie your shoes"],
  ["put on your shirt", "put on your jacket"],
  ["put on your shorts", "put on your jacket"],
  ["put on your shorts", "put on your shoes"],
];

// List the vertices that can be reached starting at 'put on your shirt'
bfs(edges, "put on your shirt");
/* =>
[
  'put on your shirt',
  'put on your jacket',
]
*/

Reverse edges

// List the vertices that can be reached starting at 'put on your jacket' when
// the edges are reversed
bfs(edges, "put on your jacket", { reverse: true });
/* =>
[
  'put on your jacket',
  'put on your shirt',
  'put on your shorts',
]
*/

Inspired by

This package uses the same data structure as toposort

License

MIT © Sigurd Fosseng