从深度搜索的路径中删除带有死胡同的节点

Question

如果我委托console.log访问了节点，我会得到很多我不想要的备用节点。

我正是开始结束节点所需的节点（不需要最短），但是我不希望算法在找到正确的路径之前所采取的所有其他路径/节点

function dfs(start, visited = new Set()) {

    console.log(start)
    
    visited.add(start);

    const destinations = adjacencyList.get(start);

    for (const destination of destinations) {

        if (destination === 'BKK') { 
            console.log(`DFS found Bangkok`)
            return;
        }
        
        if (!visited.has(destination)) {
            dfs(destination, visited);
        }

    }

}

dfs('PHX')

Answer 1

这里的想法是跟踪您访问的节点目标>目标导致纠正路径。因此，您应该在耗尽特定节点后返回，是否可以通过此节点访问end节点。

function dfs(start, visited = new Set()) {
    visited.add(start);

    const destinations = adjacencyList.get(start);
    var result = false;
    
    for (const destination of destinations) {
        
        if (destination === 'BKK') { 
            console.log(`DFS found Bangkok`);
            console.log(destination);
            return true;
        }
        
        if (!visited.has(destination)) {
             result |= dfs(destination, visited); // you can visit end from this node
        }

    }

    if(result) {
      console.log(start);
    }

    return result;
}

dfs('PHX')

请注意，这将从开始 - ＆gt;从结束到开始时以相反的顺序结束。
要从开始..-＆gt; .. finish的路径，您可以存储在某些数组（而不是Console.log）中，并在DFS完成后逆转。