运行图中的 DFS 问题

Question

节点包含（String from, String to, int time）。给定一个 HashMap，key 是一个 String，value 是一个具有相同 from 的 Node 列表。

我想编写一个函数来查找从给定起点（String start）到终点（String end）的所有可能路径。我试着写了一个 dfs 函数，但它看起来只有 return 一组结果。任何人都可以帮忙吗？

节点：字符串从，字符串到，整数时间
List> res: 节点列表的结果列表
List列表：记录当前节点的临时列表
HashMap>图：key全部来自value，value是相同from的节点列表
cur: 从一个起始值开始，改变每个dfs
结束：目的地

visited:一组记录访问过的to/from

private static void dfs(res, list,HashMap<String, List<Node>> graph,String cur, String end, visited){
    if(cur.equals(end)) {
        res.add(new ArrayList<Node>(list));
        return;
    }
    for(Node n : graph.get(cur)) {
        if (visited.contains(n.to)) continue;
        list.add(n);
        visited.add(n.to);
        dfs(res, list, graph, n.to, end, visited);
        list.remove(list.size()-1);
        visited.remove(visited.size()-1);
    }
}

Answer 1

我怀疑错误在第

行

    visited.remove(visited.size()-1);

如果您查看 Set JavaDoc，您会注意到唯一的 remove 方法是 boolean remove(Object o)，并且没有像 List 中那样按索引删除。所以这条线是有效的（感谢自动装箱）：

    visited.remove(Integer.valueOf(visited.size()-1));

这显然不是您想要的，因为它没有删除任何内容。尝试按值删除最后访问的节点：

    visited.remove(n.to);

运行图中的 DFS 问题

Issues in running DFS in a graph

java

string

depth-first-search

运行 图中的 DFS 问题

Issues in running DFS in a graph

java

string

depth-first-search

运行图中的 DFS 问题