graphs/searching/dfs

Depth-First graph searching algorithm. Returns whether there's a path between two nodes in a graph.

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

Source:

graphs/searching/dfs.js, line 27

Parameters:

Name	Type	Description
`graph`	`Array`	Adjacency matrix, which represents the graph.
`start`	`Number`	Start node.
`goal`	`Number`	Target node.

Returns:

Type:: Boolean

Returns true if path between two nodes exists.

Example

var dfs = require('../src/graphs/searching/dfs').dfs;
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 pathExists = dfs(graph, 1, 5); // true