Issues in running DFS in a graph

Question

Node contains (String from, String to, int time ). Given a HashMap, key is a String and value is a list of Node with same from.

I want to write a function to find all possible path from a given start point(String start) to end point(String end). I tried to write a dfs function, but it looks it only return one set of result. Anyone can help?

Node: String from, String to, int time
List> res: result list of list of node
List list: temporary list to record current node
HashMap> graph: key is all from value, value is list of node with the same from
cur: start with a start value and change each dfs
end: destination

visited: a set to record 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);
    }
}

SergGr SergGr · Accepted Answer · 2017-03-17T04:52:24

I suspect that the bug is at line

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

If you look at the Set JavaDoc, you'll notice that the only remove method is boolean remove(Object o) and there is no remove by index as in List. So that line is effectively (thanks to auto-boxing):

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

which is obviously not what you want as it removes nothing. Try to remove last visited node by value instead:

    visited.remove(n.to);

Issues in running DFS in a graph

1 Answers