Clone Graph

LeetCode Q 892 - Clone Graph

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.

Note:

• The number of nodes will be between 1 and 100.
• The undirected graph is a simple graph, which means no repeated edges and no self-loops in the graph.
• Since the graph is undirected, if node p has node q as neighbor, then node q must have node p as neighbor too.
• You must return the copy of the given node as a reference to the cloned graph.

Solution

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

Solution 1 : BFS

Code:

public Node cloneGraph(Node node) {
	if (node == null) return null;

	Map<Node, Node> map = new HashMap<>();

	Queue<Node> que = new LinkedList<>();
	Set<Node> set = new HashSet<>();
	que.offer(node); set.add(node);

	// copy nodes
	while (!que.isEmpty()) {
		Node curr = que.poll();
		map.put(curr, new Node(curr.val, new List<Node>()));
		for (Node nei: curr.neighbors) {
			if (set.contains(nei)) continue;
			que.offer(nei); set.add(nei);
		}
	}

	// copy edges
	for (Node curr: map.keySet) {
		for (Node nei: map.get(curr)) {
			map.get(curr).neighbors.add(map.get(nei));
		}
	}

	return map.get(node);
}

Solution 2 : DFS

Code:

public Node cloneGraph(Node root) {
	if (node == null) return null;

	Map<Node, Node> map = new HashMap<>();
	map.put(root, new Node(root.val, new ArrayList<Node>()));
		
	dfs(map, root);	
	return map.get(root);
}

private void dfs(Map<Node, Node> map, Node node) {
	for (Node nei: node.neighbors) {
		if (!map.containsKey(nei)) {
			map.put(nei, new Node(nei.value, new List<Node>()));
			dfs(map, nei);
		}
		map.get(node).neighbors.add(nei);
	}
}