JavaScript array DFS 但搜索后总是回到root

Question

我想从输入中得到输出。
它应该通过所有可能的方式传递，但不应该通过已经访问过的方式传递。
看起来和深度优先搜索类似，但是应该返回给父节点，然后再搜索。
逻辑是一个节点的最后一个元素应该与另一个节点的第一个元素相同。
并且应该从0开始，到没有节点可以搜索时结束。

input = [  
  [0, 1],
  [0, 2],
  [1, 5],
  [2, 6],
  [2, 12],
  [5, 29],
  [6, 29],
  [9, 30],
  [12, 18],
  [18, 29],
  [29, 9],
  [29, 12],
  [29, 18]
];

output =  [
  [0,1,5,29,9,30],
  [0,1,5,29,12,18,29,18],
  [0,1,5,29,12,18,29,9,30],
  [0,1,5,29,18,29,9,30],
  [0,1,5,29,18,29,12,18],
  [0,2,6,29,9,30],
  [0,2,6,29,12,18,29,9,30],
  [0,2,6,29,12,18,29,18],
  [0,2,6,29,18,29,9,30],
  [0,2,6,29,18,29,12,18],
  [0,2,12,18,29,9,30],
  [0,2,12,18,29,12],
  [0,2,12,18,29,18]
]

我试过像下面这样的递归，它显示未定义。访问对象的设置似乎未定义，但如果我编辑它，它会显示最大调用堆栈。
（用递归或迭代的方式来解决这个问题并不重要。）

请帮忙。任何评论都会有所帮助。

const seeds = input.filter( ele => ele[0] === 0);
const nodes = input.filter( ele => ele[0] !== 0);
const visited = {};

function chain(seed, nodes){
  let result = nodes.map(node => {
    if(node[0] === seed[seed.length - 1]){
      while(!visited[node]){
        visited[node]= true;
        return chain([...seed, node[0]], nodes)
      }
    }
  })
  return result;
}

function getResult(seeds, nodes){
  let result = seeds.map( seed => {
  visited[seed] = true;
    return chain(seed, nodes);
  }).flat();
  return result;
}

Answer 1

我假设你的图是一个有向图，一种“方式”将只使用一个特定的 edge 一次。

我建议先建立一个邻接表。一个由顶点键控，并且每个顶点都有一个 edges 数组（不只是相邻顶点）。

然后在 DFS 中你可以收集你访问的 edges 随着你在树中的深入，然后测试新的边缘只能添加到该列表时它尚未出现在该链中。这是与“正常”DFS 过程的主要区别，在“正常”DFS 过程中，您将在构建路径时收集顶点（而不是边）。

下面是使用生成器的实现：

function* dfs(adj, vertex=0, path=[]) {
    let leaf = true;
    for (let edge of adj[vertex]) {
        if (!path.includes(edge)) {
             yield* dfs(adj, edge[1], path.concat([edge]));
             leaf = false;
        }
    }
    if (leaf) yield path.map(edge => edge[0]).concat(vertex);
}

const input = [[0, 1], [0, 2], [1, 5], [2, 6], [2, 12], [5, 29], [6, 29], [9, 30], [12, 18], [18, 29], [29, 9], [29, 12], [29, 18]];

// Build adjacency list as key/value pairs, where key=vertex, 
//    and value=array of outgoing edges (not just the neighbors)
const adj = {};
for (let edge of input) {
    (adj[edge[0]] ??= []).push(edge);
    adj[edge[1]] ??= [];
}

// Output paths
for (let path of dfs(adj)) console.log(JSON.stringify(path));

输入图就是你的图：

输出为：

[0,1,5,29,9,30]
[0,1,5,29,12,18,29,9,30]
[0,1,5,29,12,18,29,18]
[0,1,5,29,18,29,9,30]
[0,1,5,29,18,29,12,18]
[0,2,6,29,9,30]
[0,2,6,29,12,18,29,9,30]
[0,2,6,29,12,18,29,18]
[0,2,6,29,18,29,9,30]
[0,2,6,29,18,29,12,18]
[0,2,12,18,29,9,30]
[0,2,12,18,29,12]
[0,2,12,18,29,18]

JavaScript array DFS 但搜索后总是回到root

JavaScript array DFS but always back to root after searching

javascript

arrays

recursion

for-loop

depth-first-search