Problem overview
The method cloneGraph receives node, node 1 of a connected, undirected graph, or None when the graph is empty. It returns a deep copy of the graph: the copy of node 1.
The lesson provides the node class, shown in the starter code as a comment. A Node has a val and a list neighbors of other nodes. Node i has the value i. A deep copy consists of exactly n brand-new nodes, one per original node, with the same values. The neighbor list of each new node holds the new nodes of the original node's neighbors, in the same order. No node of the copy may be a node of the original graph.
The examples show graphs as adjacency lists, where entry i - 1 holds the values of node i's neighbors. For [[2, 4], [1, 3], [2, 4], [1, 3]] the graph is a square of four nodes (1 - 2 - 3 - 4 - 1), and the copy is another square of four new nodes. For [[]] the graph is one node with no neighbors. For [] the function gets None and returns None.
The statement asks for O(V + E) time and O(V) extra space, where V is the number of nodes and E the number of edges.
Approach: one copy per node, found through a dict
Copying a graph is harder than copying a list or a tree, because nodes can be reached by several paths and the graph can contain cycles. Two things can go wrong:
- A neighbor is copied twice, once from each of two nodes that reach it. The copy then has more than
nnodes, and links that should meet at one node lead to two. - The walk goes around a cycle forever.
One dict fixes both. It maps each original node to its copy. A node's copy is made the first time the search meets the node. Whenever the search meets that node again, it finds the copy in the dict instead of making a new one.
The search is a breadth-first search with a queue. A node joins the queue at the moment its copy is made, so each node is queued exactly once. When a node leaves the queue, its copy has to receive its neighbor list: for each neighbor of the original, the copy of that neighbor is appended to the copy's list. Neighbors are visited in the original order, so the copied lists keep that order.
On the square graph, the search runs like this:
took 1 made [2, 4] queue [2, 4] copy list [2, 4]
took 2 made [3] queue [4, 3] copy list [1, 3]
took 4 made [] queue [3] copy list [1, 3]
took 3 made [] queue [] copy list [2, 4]
Each line shows the node taken from the queue, the nodes whose copies were created while looking at its neighbors, the queue afterwards, and the values in the neighbor list of its copy. When node 2 is taken, its neighbor 1 already has a copy, so only the link is added.
A depth-first search with the same dict also works. The queue version avoids deep recursion, which matters because a graph of 50,000 nodes in a long chain would exceed Python's default recursion limit.
Step by step
- Handle the empty graph. If
node is None, returnNone. The next lines read the node's value, which needs a node. - Create
copies, a dict with one entry:nodemapped toNode(node.val). The dict finds the copy of any node met so far, and it also tells which nodes have been met. - Create a
dequenamedqueueholding justnode. Every node in it already has its copy, and what the copy still lacks is its neighbors. - Loop while
queueis not empty. An empty deque counts as false, sowhile queue:is enough. - Take the front node into
currentwithpopleft(). Its copy's neighbor list is filled in now. - Loop over
current.neighborswithneighbor. Over the whole run, each edge is seen twice, once from each end. - Check
neighbor not in copies.inon a dict looks at its keys, so this means the search meets the node for the first time. - Make the copy:
copies[neighbor] = Node(neighbor.val). A node that has a copy never gets a second one. - Queue the neighbor, still inside the
if, so its own neighbors are copied when it leaves the queue. - Link the copies, back at the
if's indentation: appendcopies[neighbor]tocopies[current].neighbors. This is the key line. The copy ofcurrentpoints to the copy ofneighbor, never toneighboritself. - Return
copies[node]after the loop, the copy of node 1. The graph is connected, so every node was reached.
The solution in Python
class Solution:
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
if node is None:
return None
copies = {node: Node(node.val)}
queue = deque([node])
while queue:
current = queue.popleft()
for neighbor in current.neighbors:
if neighbor not in copies:
copies[neighbor] = Node(neighbor.val)
queue.append(neighbor)
copies[current].neighbors.append(copies[neighbor])
return copies[node]
Python details worth a closer look:
- Nodes as dict keys. The
Nodeclass doesn't define its own equality or hash, so Python compares and hashes its instances by identity. Two different nodes are two different keys, even when they have the sameval.Node(1) == Node(1)isFalse. That is exactly what the dict needs. - The new nodes start with an empty list. The class uses
neighbors if neighbors is not None else [], so eachNode(val)gets its own fresh list. That's why appending tocopies[current].neighborsnever touches another node's list. dequefor the queue.popleft()andappend()take constant time.list.pop(0)would shift every element and cost linear time per call. The lesson's editor already makesdequeavailable. In a file of your own, addfrom collections import deque.- Appending the original would be a shallow copy. A line such as
copies[current].neighbors.append(neighbor)would let the copy point into the original graph. The tests report any node of the copy that belongs to the original. - Truthiness.
while queue:relies on an emptydequebeing false.
Complexity
Time: O(V + E). Each node is queued once and each copy is created once. Each edge is looked at twice, once from each end, with a dict lookup that takes constant time on average.
Space: O(V). The dict holds one entry per node, and the queue never holds more than V nodes. The copy itself is also O(V + E), since it is the output.
Edge cases and common mistakes
- The empty graph. Without the
Nonecheck,node.valraisesAttributeError. - A single node.
[[]]gives one new node with an empty neighbor list. The loop takes node 1, finds no neighbors and ends. - Cycles. In the square graph, node 4 is a neighbor of both 1 and 3. Because the dict is checked before copying, it is copied once and queued once.
- Copying before checking. Writing
copies[neighbor] = Node(neighbor.val)without theifwould replace an existing copy, and earlier links would point to a node that's no longer in the dict. - Queueing outside the
if. A node queued each time it is met would be processed several times, and its copy would get duplicate neighbors. - Losing the order. Neighbors must be appended in the original order. For a node whose original list is
[3, 2], the copy's list is also[3, 2].
Testing
adjList = [[2, 4], [1, 3], [2, 4], [1, 3]]gives[[2, 4], [1, 3], [2, 4], [1, 3]], with 4 new nodes and none shared with the original.adjList = [[]]gives[[]].adjList = []gives[].adjList = [[2], [1]]gives[[2], [1]]: two nodes pointing at each other.adjList = [[2, 3], [1, 3], [1, 2]]gives[[2, 3], [1, 3], [1, 2]], a triangle.adjList = [[3, 2], [1, 3], [1, 2]]gives[[3, 2], [1, 3], [1, 2]]: the order of neighbors is kept.
