在图形中运行DFS的问题

Question

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

我想写一个函数来找到从给定起点（字符串起始）到终点（字符串结束）的所有可能路径。我试图编写一个dfs函数，但它看起来只返回一组结果。有人能帮忙吗？

>

节点：String from、String to、int time

list>res:节点列表的结果列表

列表列表：记录当前节点的临时列表

HashMap>图：键为全部from值，值为具有相同from的节点列表

cur:从一个起始值开始并更改每个DF

结束：目标

访问过的：记录访问过/访问过的集合

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);

如果查看setJavaDoc，您会注意到唯一的remove方法是boolean remove(Object)，而没有list中的remove by index。因此该行有效地（由于自动装箱）：

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

这显然不是你想要的，因为它什么也不删除。改为尝试按值删除上次访问的节点：

    visited.remove(n.to);