获取两节点间的所有路径(非递归)

要在 JavaScript 中使用非递归的方式获取两个节点之间的所有路径，我们可以使用栈（Stack）来实现深度优先搜索（DFS），如果使用递归，数据量大可能会内存溢出；

class customGraph {
    nodes: Map<any, any>;
    constructor() {
        this.nodes = new Map();
    }
    addNode(node: string) {
        this.nodes.set(node, []);
    }
    addEdge(node1: string, node2: string) {
        this.nodes.get(node1).push(node2);
        // this.nodes.get(node2).push(node1);
    }
    dfs(graph: Map<any, any>, current: string, end: string, depth: number, path: any[], paths: any[][], visited: Set<unknown>) {
        if (current === end) {
            paths.push([...path]);
            return;
        }
        if (depth === 0) {
            return;
        }
        visited.add(current);
        for (let neighbor of graph.get(current)) {
            if (!visited.has(neighbor)) {
                path.push(neighbor);
                this.dfs(graph, neighbor, end, depth - 1, path, paths, visited);
                path.pop();
            }
        }
        visited.delete(current);
    }
    getAllPaths(node1: string, node2: string) {
        const paths: any[] = [];
        const visited = new Set();
        const graph = this.nodes
        for (let depth = 1; depth <= 4; depth++) {
            this.dfs(graph, node1, node2, depth, [node1], paths, visited);
        }
        console.log('paths信息:', paths);
        return paths;
    }
}
export default customGraph

// index.tsx

// 创建一个图
let graph = new customGraph();
graph.addNode('A');
graph.addNode('B');
graph.addNode('C');
graph.addNode('D');
graph.addNode('E');

graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'D');
graph.addEdge('C', 'E');
graph.addEdge('D', 'E');

let node1 = 'A';
let node2 = 'E';

let paths = graph.getAllPaths(node1, node2);
console.log(paths);