5

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

据我了解，使用递归，深度优先搜索不需要显式堆栈结构，所以我想知道是否可以通过某种方式不使用显式堆栈来进一步简化下面的代码：

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 +"]");
    }
}

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

4

4 回答 4

1

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

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

于 2010-01-09T11:15:50.917 回答
0

只需在节点结构中添加一个额外的字段，即“已访问”字段。这将是最快的。您必须在之后（或在进行搜索之前）取消标记所有节点。

或者，只需在散列表中散列节点的 id。这将比堆栈更快地检查。如果您没有节点的 id，最好创建一个，以帮助调试、输出等。

您确实需要额外的空间，但向每个节点添加一个布尔字段将需要最少的空间，因为它将是每个节点 1 位，而堆栈每个节点需要 1 个指针。

您实际上并不需要距离截止，因为您正在搜索有限图并且您只访问每个节点一次，因此您将访问 N 节点图中的最多 N 个节点。如果您正在搜索无限空间，例如在进行状态空间搜索时（例如，prolog 解释器搜索证明），则需要深度截止。

于 2010-01-09T22:11:19.210 回答
0

您不需要访问过的节点。只需将当前子节点传递给递归方法而不是访问节点参数，并使用返回值来承载路径。

如果您可以逐个元素处理路径元素，即重写 printPath() 以便每个元素可以调用一次，则只需要键类型作为返回类型。如果你想接收整个路径，你需要一个键值列表作为返回类型。

实际上，您相对接近解决方案。只需使用递归方法调用的调用堆栈来表示路径。

于 2010-01-13T17:31:40.433 回答
-1

编辑：这个答案完全是题外话，是基于对问题的误解而发布的。

您的 DFS 实施存在一些问题。是的，它以深度优先的方式访问所有节点，并最终设法找到了 START 和 END 之间的路径，但它不会尝试检查已经访问过的节点并无缘无故地保留堆栈。您不会陷入循环无限递归的唯一原因是因为您限制了最大路径长度，并且在所有顶点对之间具有多个不同路径的图上您仍然需要很长时间。

您使用堆栈的唯一目的是将要访问的节点传递到 dfs 函数旁边。您可以简单地摆脱堆栈并直接传递节点。

所以，而不是

private void depthFirst(WeightedDirectedGraph graph, Stack<String> visited) {
   ...
   visited.push(child);
   ...
   depthFirst(graph, visited);

您可以简单地将其写为

private void depthFirst(WeightedDirectedGraph graph, String node) {
   ...
   //visited.push(child); <-- No longer needed
   ...
   depthFirst(graph, child);

您正在使用您已命名为“已访问”的数据结构（堆栈），但您并未使用它来存储/标记已访问过哪些节点以避免重新访问。

您可以修改现有代码以拥有一个名为visited 的Set（使其成为全局/类变量或将其传递给您对堆栈所做的递归调用），您可以在其中保留所有已访问的节点，并且仅在那些节点上调用depthFirst()尚未在该集合中。

那应该使您的代码看起来像这样

private void depthFirst(WeightedDirectedGraph graph, String node, Set<String> visited) {
   visited.add(node); // mark current node as visited
   ...
   //visited.push(child); <-- No longer needed
   ...
   if (!visited.contains(child)){ // don't visit nodes we have worked on already
      depthFirst(graph, child);
   }

到目前为止，我的回答是尝试修改您的代码以使其正常工作。但在我看来，您需要更好地了解 DFS 的实际含义以及它的实际工作原理。阅读任何优秀的算法/图论书籍的相关章节将对您有很大帮助。我会推荐 CLRS（它有一个关于简单图遍历的非常好的章节），但任何好书都应该这样做。一个简单而正确的递归 DFS 可以使用数组以更简单的方式实现，而不必求助于堆栈或集合。

编辑：我没有提到替换堆栈后如何检索路径。这可以通过使用在探索时存储每个节点的父节点的 Map 来轻松完成。可以使用递归 printPath(String node) 函数获取路径（如果找到），该函数打印传递给它的节点并在其父节点上再次调用自身。

于 2010-01-09T12:58:42.920 回答