Clone an Undirected Graph

JavaView on GFG

Time: O(V+E)

Space: O(V)

Intuition

BFS/DFS with a HashMap from original node to clone. For each original node, create clone and process its neighbors.

Algorithm

1Map: original -> clone. BFS queue.
2For each neighbor of original: if not in map, create clone and add to queue. Add clone to cloneNode.neighbors.

Common Pitfalls

•Use visited map to avoid infinite loops in cyclic graphs.

Clone an Undirected Graph.java

Java

// Approach: BFS/DFS with a HashMap mapping original nodes to clones.
// For each neighbor, create clone if absent and add to cloned adjacency list.
// Time: O(V+E) Space: O(V)
import java.util.*;

class Node {
    int val;
    ArrayList<Node> neighbors;

    public Node() {
        val = 0;
        neighbors = new ArrayList<>();
    }

    public Node(int val) {
        this.val = val;
        neighbors = new ArrayList<>();
    }

    public Node(int val, ArrayList<Node> neighbors) {
        this.val = val;
        this.neighbors = neighbors;
    }
}

class Solution {
    Node cloneGraph(Node node) {
        Set<Node> vis = new HashSet<>();
        return dfs(node, vis);
    }

    private Node dfs(Node node, Set<Node> vis) {
        vis.add(node);
        Node copyNode = new Node(node.val);
        for (Node neighbour : node.neighbors) {
            if (!vis.contains(neighbour))
                copyNode.neighbors.add(dfs(neighbour, vis));
        }

        return copyNode;
    }
}

Was this solution helpful?