Posted on | Edited on

https://leetcode.com/problems/clone-graph/

1
2
3
4
5
6
7
8
9
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {}
    public Node(int _val,List<Node> _neighbors) {
        val = _val; neighbors = _neighbors;
    }
}

DFS_1: Recursion
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    HashMap<Node,Node> map=new HashMap<>();
    public Node cloneGraph(Node node) {
        if(node==null) return node;
        if(map.containsKey(node)) return map.get(node);
        Node cloneNode=new Node(node.val,new ArrayList<Node>());
        map.put(node,cloneNode);
        for(Node neighbor:node.neighbors){
            cloneNode.neighbors.add(cloneGraph(neighbor));
        }
        return cloneNode;
    }
}

DFS_2: Iteration
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public Node cloneGraph(Node node) {
        if(node==null) return node;
        Map<Node,Node> visited=new HashMap<>();
        visited.put(node,new Node(node.val,new ArrayList<>()));
        LinkedList<Node> stack=new LinkedList<>();
        stack.push(node);
        while(!stack.isEmpty()){
            Node stackNode=stack.pop();
            for(Node neighbor:stackNode.neighbors){
                if(!visited.containsKey(neighbor)){
                    visited.put(neighbor,new Node(neighbor.val,new ArrayList<>()));
                    stack.push(neighbor);
                }
                visited.get(stackNode).neighbors.add(visited.get(neighbor));
            }
        }
        return visited.get(node);
    }
}

BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return node;
        // Hash map to save the visited node and it's respective clone
        // as key and value respectively. This helps to avoid cycles.
        HashMap<Node, Node> visited = new HashMap<>();
        // Put the first node in the queue
        LinkedList<Node> queue = new LinkedList<Node> ();
        queue.offer(node);
        // Clone the node and put it in the visited dictionary.
        visited.put(node, new Node(node.val, new ArrayList<>()));
        // Start BFS traversal
        while (!queue.isEmpty()) {
            // Pop a node say "n" from the from the front of the queue.
            Node n = queue.poll();
            // Iterate through all the neighbors of the node "n"
            for (Node neighbor: n.neighbors) {
                if (!visited.containsKey(neighbor)) {
                    // Clone the neighbor and put in the visited, if not present already
                    visited.put(neighbor, new Node(neighbor.val, new ArrayList<>()));
                    // Add the newly encountered node to the queue.
                    queue.add(neighbor);
                }
                // Add the clone of the neighbor to the neighbors of the clone node "n".
                visited.get(n).neighbors.add(visited.get(neighbor));
            }
        }
        // Return the clone of the node from visited.
        return visited.get(node);
    }
}

0%