java - 用于递归深度优先搜索以存储路径的额外空间

Question

我正在使用深度优先搜索来识别有向加权图中的路径，同时重新访问属于循环的节点，并根据行进的总距离或从源节点停止来设置截止条件。

据我所知，通过递归，深度优先搜索不需要显式堆栈结构，所以我想知道我是否可以通过某种方式在没有显式堆栈的情况下进一步简化我的代码:

public class DFSonWeightedDirectedGraph {

    private static final String START = "A";
    private static final String END = "E";
    private int pathLength = 0;
    private int stops = 0;

    public static void main(String[] args) {
        //this is a directed weighted graph
        WeightedDirectedGraph graph = new WeightedDirectedGraph();
        graph.addEdge("A", "B", 15);
        graph.addEdge("A", "D", 15);
        graph.addEdge("A", "E", 27);
        //(...) more edges added


        Stack<String> visited = new Stack<String>();        
        visited.push(START);

        new DFSonWeightedDirectedGraph().depthFirst(graph, visited);
    }

    private void depthFirst(WeightedDirectedGraph graph, Stack<String> visited) {

        Collection<Map.Entry<String, Integer>> tree_of_children 
            = graph.get_tree_of_children(visited.peek());

        for (Map.Entry<String, Integer> child : tree_of_children) {


            if(pathLength + child.getValue()>= 20){
                continue;
            }       


            visited.push(child.getKey());
            pathLength += child.getValue();
            stops += 1;         

            if (child.getKey().equals(END)) {
                printPath(visited);
            }

            depthFirst(graph, visited); 
            visited.pop();  
            pathLength -= child.getValue();
            stops -= 1; 
        }
    }

    private void printPath(Stack<String> visited) {
        for (String node : visited) {
            System.out.print(node);
            System.out.print(" ");
        }
        System.out.println("[path length: "+pathLength +
                " stops made: " + stops +"]");
    }
}

但是，其他没有显式堆栈结构的递归实现通常会考虑已经访问过的节点，方法是将它们着色为白色、灰色或黑色。那么，在我允许重访的情况下，需要记录路径，是否绝对需要显式堆栈？感谢您提供更简单的替代方案的任何建议。

Answer 1

如果你必须保存路径，你需要一个数据结构。你的堆栈没问题；您可以用另一种数据结构替换它，但不能删除它。

如果直接打印路径(不记录)就可以了，就不需要栈了。然后您可以更改方法签名以仅获取图形和实际节点(可能还有实际路径长度和“停靠点”)。