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

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

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

如果可以直接打印路径（而不记录它），则不需要堆栈。然后，您可以更改方法签名以仅获取图形和实际节点（也许还有实际路径长度和“停止点”）。