要在 JavaScript 中使用非遞歸的方式獲取兩個(gè)節(jié)點(diǎn)之間的所有路徑，我們可以使用棧（Stack）來(lái)實(shí)現(xiàn)深度優(yōu)先搜索（DFS），如果使用遞歸，數(shù)據(jù)量大可能會(huì)內(nèi)存溢出桩引；
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
// 創(chuàng)建一個(gè)圖
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);
