graphs/searching/bfs

Breath-First graph searching algorithm. Returns the shortest path between startNode and targetNode.

Time complexity: O(|V|^2).

Source:

graphs/searching/bfs.js, line 15

Parameters:

Name	Type	Description
`graph`	`Array`	Adjacency matrix, which represents the graph.
`startNode`	`Number`	Start node.
`targetNode`	`Number`	Target, which should be reached.

Returns:

Type:: Array

Shortest path from startNode to targetNode.

Example

var bfs = require('path-to-algorithms/src/graphs/searching/bfs').bfs;
var graph = [[1, 1, 0, 0, 1, 0],
             [1, 0, 1, 0, 1, 0],
             [0, 1, 0, 1, 0, 0],
             [0, 0, 1, 0, 1, 1],
             [1, 1, 0, 1, 0, 0],
             [0, 0, 0, 1, 0, 0]];
var shortestPath = bfs(graph, 1, 5); // [1, 2, 3, 5]