0133. Clone Graph
https://leetcode.com/problems/clone-graph
Description
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 value (int
) and a list (List[Node]
) of its neighbors.
class Node {
public int val;
public List<Node> neighbors;
}
Test case format:
For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1
, the second node with val == 2
, and so on. The graph is represented in the test case using an adjacency list.
An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.
The given node will always be the first node with val = 1
. You must return the copy of the given node as a reference to the cloned graph.
Example 1:

**Input:** adjList = [[2,4],[1,3],[2,4],[1,3]]
**Output:** [[2,4],[1,3],[2,4],[1,3]]
**Explanation:** There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
Example 2:

**Input:** adjList = [[]]
**Output:** [[]]
**Explanation:** Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.
Example 3:
**Input:** adjList = []
**Output:** []
**Explanation:** This an empty graph, it does not have any nodes.
Example 4:

**Input:** adjList = [[2],[1]]
**Output:** [[2],[1]]
Constraints:
The number of nodes in the graph is in the range
[0, 100]
.1 <= Node.val <= 100
Node.val
is unique for each node.There are no repeated edges and no self-loops in the graph.
The Graph is connected and all nodes can be visited starting from the given node.
ac1: BFS
/**
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* List<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) return null;
Map<Integer,UndirectedGraphNode> map = new HashMap<Integer,UndirectedGraphNode>();
UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
map.put(node.label, newNode);
Queue<UndirectedGraphNode> q = new LinkedList<UndirectedGraphNode>();
q.offer(node);
while (!q.isEmpty()) {
UndirectedGraphNode head = q.poll();
for (UndirectedGraphNode adj : head.neighbors) {
if (!map.containsKey(adj.label)) {
UndirectedGraphNode clone = new UndirectedGraphNode(adj.label);
map.put(adj.label, clone);
q.offer(adj);
}
map.get(head.label).neighbors.add(map.get(adj.label));
}
}
return newNode;
}
}
ac2: DFS
best answer, this one is easier to understand and more natural.
public class Solution {
Map<Integer,UndirectedGraphNode> map;
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
map = new HashMap<Integer,UndirectedGraphNode>();
return clone(node);
}
private UndirectedGraphNode clone(UndirectedGraphNode node) {
if (node == null) return null;
if (map.containsKey(node.label)) return map.get(node.label);
UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
map.put(node.label, newNode);
for (UndirectedGraphNode neighbor : node.neighbors) {
map.get(newNode.label).neighbors.add(clone(neighbor));
}
return newNode;
}
}
my original version
public class Solution {
Map<Integer,UndirectedGraphNode> map;
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) return null;
map = new HashMap<Integer,UndirectedGraphNode>();
clone(node);
return map.get(node.label);
}
private void clone(UndirectedGraphNode node) {
UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
map.put(node.label, newNode);
for (UndirectedGraphNode neighbor : node.neighbors) {
if (!map.containsKey(neighbor.label)) {
clone(neighbor);
}
map.get(node.label).neighbors.add(map.get(neighbor.label));
}
}
}
/**
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* List<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
public class Solution {
Map<Integer, UndirectedGraphNode> map = new HashMap<>();
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
// edge cases
if (node == null) return node;
UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
map.put(node.label, newNode);
for (UndirectedGraphNode n : node.neighbors) {
if (map.containsKey(n.label)) { // has been cloned before, get it
newNode.neighbors.add(map.get(n.label));
} else {
UndirectedGraphNode tmp = cloneGraph(n);
newNode.neighbors.add(tmp);
}
}
return newNode;
}
}
Last updated
Was this helpful?