Problem overview
CloneGraph receives node, node 1 of a connected, undirected graph, and returns a deep copy of the whole graph: the copy of node 1. The lesson provides the Node class: it has a public int val, a public List<Node> neighbors, and a constructor Node(int x) that sets the value and starts an empty neighbor list.
A deep copy has one brand-new node for every original node, with the same value. Each new node's neighbor list holds the new nodes of the original's neighbors, in the same order. No node of the copy may be a node of the original. For an empty graph, node is null and the method returns null.
In the first example the four nodes form a square: node 1 is next to 2 and 4, node 2 to 1 and 3, node 3 to 2 and 4, and node 4 to 1 and 3. The copy has the same shape, built from four new nodes.
Approach: a map from original to copy
Copying a node is easy; the difficulty is the links. A node's neighbors link back to it, so the graph is full of cycles, and a naive recursive copy would chase them forever. It would also need to know whether a neighbor has already been copied, so that two nodes pointing at the same neighbor point at the same new node and not at two different ones.
Both problems are solved by a Dictionary<Node, Node> from each original node to its copy. A node's copy is made the first time the search meets it. That is also the moment the node joins the queue of a breadth-first search. A node that already has a copy is never copied or queued again, which stops the search from circling a cycle.
When a node leaves the queue, the copies of its neighbors are appended, in order, to its own copy's list.
Step by step
- Handle the empty graph. If
nodeisnull, returnnull. The next lines readnode.val. - Create
copies, aDictionary<Node, Node>.Nodedoes not define its ownEqualsorGetHashCode, so the dictionary compares nodes by identity: two different nodes are different keys, even with the same value. - Copy node 1:
copies[node] = new Node(node.val). The map both finds the copy of any node met so far and tells which nodes have been met. - Create a
Queue<Node>andEnqueue(node). Every node in the queue has a copy already; what the copy lacks is its neighbor list. - Loop while
queue.Count > 0, taking the front node withDequeueintocurrent. - Loop over
current.neighborswithforeach. Every edge is seen twice, once from each end, so the total work is proportional to nodes plus edges. - If
!copies.ContainsKey(neighbor), this is the first meeting: make its copy andEnqueueit. A node enters the queue only when its copy is made, so each node is queued once. - Link the copies. Add
copies[neighbor]tocopies[current].neighbors. This line is the heart of the solution: the copy ofcurrentpoints to the copy ofneighbor, never toneighboritself. - Return
copies[node], the copy of node 1, after the loop.
The solution in C#
class Solution {
public Node CloneGraph(Node node) {
if (node == null) {
return null;
}
Dictionary<Node, Node> copies = new Dictionary<Node, Node>();
copies[node] = new Node(node.val);
Queue<Node> queue = new Queue<Node>();
queue.Enqueue(node);
while (queue.Count > 0) {
Node current = queue.Dequeue();
foreach (Node neighbor in current.neighbors) {
if (!copies.ContainsKey(neighbor)) {
copies[neighbor] = new Node(neighbor.val);
queue.Enqueue(neighbor);
}
copies[current].neighbors.Add(copies[neighbor]);
}
}
return copies[node];
}
}
The C# details worth knowing:
- Reading
copies[x]for a missing key throwsKeyNotFoundException. The code is safe because a neighbor's copy is always made, in theif, beforecopies[neighbor]is read on the next line. Dictionaryuses reference equality for a class that does not overrideEquals, which is what this problem needs. ADictionary<int, Node>keyed byvalwould also work here because values are unique, but identity does not depend on that.Queue<T>hasEnqueueat the back,Dequeuefrom the front, andCount. NoteCount, notLength.Node,Dictionary,QueueandListcome from the lesson's setup, so you do not addusinglines in the editor. In a file of your own you would needusing System.Collections.Generic;.
Complexity
Time: O(V + E), where V is the number of nodes and E the number of edges. Each node is queued once, and each node's neighbor list is read once, which covers every edge twice.
Space: O(V) for the dictionary and the queue, besides the copy itself.
A recursive depth-first copy with the same dictionary also works, but a long path of tens of thousands of nodes would make the recursion deep. The queue has no such limit.
Edge cases and common mistakes
- Empty graph.
nullin,nullout. - A single node. A node with value 1 and no neighbors gives a new node with value 1 and an empty list. It is not the original object.
- Cycles. In the square graph, node 1 is a neighbor of node 2 and node 2 is a neighbor of node 1. The dictionary check stops the search from copying either twice.
- Adding the original neighbor to the copy's list. The copy would then share nodes with the original graph, which the tests reject.
- Making the copy inside the queue loop instead of at the first meeting. A node can be reached from several neighbors before it leaves the queue, and would get several copies.
- Neighbor order. The copy's list follows the original's order, because neighbors are added in the order the original lists them.
Testing
Walking the copy of the four-node square from the returned node, and printing each node's neighbors and whether the node is one of the originals, gives:
1: 2,4 sameObjectAsOriginal=False
2: 1,3 sameObjectAsOriginal=False
4: 1,3 sameObjectAsOriginal=False
3: 2,4 sameObjectAsOriginal=FalseThe nodes appear in the order the walk reaches them: 1, 2, 4, 3. Passing null returns null. A single node with value 1 and no neighbors gives a node with value 1, an empty neighbor list, and a different object from the original.
