/**
* Perform a breadth-first search on a graph or tree.
* @param {Object} root - The root node to start the search from.
* @param {Function} visit - A function to call for each visited node, return true to end up the search.
* @param {Function} getChildren - A function to get the children of a node.
* @returns {Object} The node found
*/
export function bfs(root, visit, getChildren) {
const queue = Array.isArray(root) ? [...root] : [root];
const visited = new Set();
visited.add(root);
let found;
while (queue.length > 0) {
const node = queue.shift();
if (visit(node)) {
found = node;
break;
}
const children = getChildren(node);
children?.forEach((child) => {
if (!visited.has(child)) {
visited.add(child);
queue.push(child);
}
});
}
return found;
}
/**
* Perform a depth-first search on a graph or tree.
* @param {Object} root - The root node to start the search from.
* @param {Function} visit - A function to call for each visited node, return true to end up the search.
* @param {Function} getChildren - A function to get the children of a node.
* @returns {Object} The node found
*/
export function dfs(root, visit, getChildren) {
const stack = Array.isArray(root) ? [...root].reverse() : [root];
const visited = new Set();
let found;
while (stack.length > 0) {
const node = stack.pop();
if (!visited.has(node)) {
if (visit(node)) {
found = node;
break;
}
visited.add(node);
const children = getChildren(node);
if (!children || children.length === 0) {
continue;
}
const [leftNode, ...right] = children;
right.reverse().forEach((child) => {
stack.push(child);
});
stack.push(leftNode);
}
}
return found;
}