40 lines
857 B
JavaScript
40 lines
857 B
JavaScript
var _ = require("../lodash");
|
|
|
|
module.exports = dfs;
|
|
|
|
/*
|
|
* A helper that preforms a pre- or post-order traversal on the input graph
|
|
* and returns the nodes in the order they were visited. This algorithm treats
|
|
* the input as undirected.
|
|
*
|
|
* Order must be one of "pre" or "post".
|
|
*/
|
|
function dfs(g, vs, order) {
|
|
if (!_.isArray(vs)) {
|
|
vs = [vs];
|
|
}
|
|
|
|
var acc = [],
|
|
visited = {};
|
|
_.each(vs, function(v) {
|
|
if (!g.hasNode(v)) {
|
|
throw new Error("Graph does not have node: " + v);
|
|
}
|
|
|
|
doDfs(g, v, order === "post", visited, acc);
|
|
});
|
|
return acc;
|
|
}
|
|
|
|
function doDfs(g, v, postorder, visited, acc) {
|
|
if (!_.has(visited, v)) {
|
|
visited[v] = true;
|
|
|
|
if (!postorder) { acc.push(v); }
|
|
_.each(g.neighbors(v), function(w) {
|
|
doDfs(g, w, postorder, visited, acc);
|
|
});
|
|
if (postorder) { acc.push(v); }
|
|
}
|
|
}
|