Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | 16x 51x 41x 41x 21x 41x 35x 41x 20x 16x 12x 12x 41x 12x 12x 12x 18x 2x 16x 10x | import Graph from '../Graph';
/**
* @description DFS traversal.
* @description.zh-CN DFS 遍历。
*/
const doDFS = <NodeIDType = any>(
graph: Graph<NodeIDType>,
node: NodeIDType,
postorder: boolean,
visited: NodeIDType[],
navigator: (n: NodeIDType) => NodeIDType[],
result: NodeIDType[],
) => {
if (!visited.includes(node)) {
visited.push(node);
if (!postorder) {
result.push(node);
}
navigator(node).forEach((n) =>
doDFS<NodeIDType>(graph, n, postorder, visited, navigator, result),
);
if (postorder) {
result.push(node);
}
}
};
/**
* @description DFS traversal.
* @description.zh-CN DFS 遍历。
*/
const dfs = <NodeIDType = any>(
graph: Graph<NodeIDType, any, any, any>,
node: NodeIDType | NodeIDType[],
order: 'pre' | 'post',
) => {
const nodes = Array.isArray(node) ? node : [node];
const navigator = (n: NodeIDType) =>
(graph.isDirected() ? graph.successors(n) : graph.neighbors(n))!;
const results: NodeIDType[] = [];
const visited: NodeIDType[] = [];
nodes.forEach((node) => {
if (!graph.hasNode(node)) {
throw new Error('Graph does not have node: ' + node);
} else {
doDFS(graph, node, order === 'post', visited, navigator, results);
}
});
return results;
};
export default dfs;
|