Java DFS Recursion Wouldn't Pass {0,0,0}


  • 2
    G
    private Set<UndirectedGraphNode> visited = new HashSet<>();
    
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node == null){
            return null;
        }
    
        UndirectedGraphNode clone = new UndirectedGraphNode(node.label);
        visited.add(node);
    
        for(int i = 0; i < node.neighbors.size(); i++){
            UndirectedGraphNode neighbor = node.neighbors.get(i);
            // only recurse once
            if(!visited.contains(neighbor)){
                clone.neighbors.add(cloneGraph(neighbor));
            }else{
                clone.neighbors.add(new UndirectedGraphNode(neighbor.label));
            }
        }
        return clone;
    }
    

    The thoughts of this algorithm is to only start a new sub-call/recursion if a node is not visited yet, otherwise just make a new node and add to neighbors list.

    The {0,0,0} test case results in {0,0,0#0#0} instead of {0,0,0}, I ran my code locally with {0,0,0} and it was able to print out correct results. Any help would be appreciated.


  • 0
    G

    Finally I realized what the problem is. Instead of creating a new copy if a node is visited, I should use the reference to the original copy, see below.

    private Map<UndirectedGraphNode,UndirectedGraphNode> visited = new HashMap<>();
    
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node == null){
            return null;
        }
    
        UndirectedGraphNode clone = new UndirectedGraphNode(node.label);
        visited.put(node, clone);
    
        for(int i = 0; i < node.neighbors.size(); i++){
            UndirectedGraphNode neighbor = node.neighbors.get(i);
            // only recurse once
            if(!visited.containsKey(neighbor)){
                clone.neighbors.add(cloneGraph(neighbor));
            }else{
                clone.neighbors.add(visited.get(neighbor));
            }
        }
        return clone;
    }

  • 0
    E

    Encountered the same problem, your solution is correct, but why should it be a reference to the original copy instead of a new copy? I still dont understand.


  • 0
    W

    The key is original copy but the value is new one.


  • 0
    S

    @gwang8 said in Java DFS Recursion Wouldn't Pass {0,0,0}:

    I can't understand the test case {0,0,0}. The statement "Nodes are labeled uniquely." made me think that every node has unique label value. So, what's the meaning of this test case? Can you help me ?


  • 0
    G

    @saleo In this case, 0 is the node and it has two self connections, thus 0,0,0


  • 0
    G

    @ender725 A node could be visited multiple times, we don't want to create a new clone every time we visit it. Therefore we always want to use the clone we created when visiting a node for the first time, which is visited.get(neighbor)


  • 0
    S

    @gwang8
    I have solved this problem. thanks a lot !


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.