Problem overview
The method cloneGraph receives node, node 1 of a connected, undirected graph, or nil when the graph is empty. It returns a deep copy of the graph: the copy of node 1. A deep copy is made 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's neighbors, in the same order. No node of the copy may be a node of the original graph.
The lesson provides the node class, shown in the starter code as a comment: Node has a val, an array neighbors of Node, and an initializer init(_ val: Int) that starts with no neighbors. It is Hashable by identity, so a node can be a dictionary key and two different nodes are different keys even when their values are equal.
The examples describe a graph by adjacency lists, where entry i - 1 lists the values of node i's neighbors. For [[2, 4], [1, 3], [2, 4], [1, 3]] the graph is a square of 4 nodes, and the copy has the same shape, made of 4 new nodes. For [[]] the graph is a single node with no neighbors, and the copy is one new node with the value 1. For [] the function gets nil and returns nil.
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 dictionary
The difficulty is that nodes point to each other in both directions. Copying a node's neighbors one by one would copy node 1, then its neighbor 2, then 2's neighbor 1 again, and go around forever. The fix is a dictionary from each original node to its copy. A node gets a copy the first time the search meets it. When the search meets it again, the dictionary already has the copy, so the node is neither copied nor visited again.
The search is a breadth-first search. The queue holds nodes whose copies exist but whose neighbor lists are still empty. When a node leaves the queue, the code walks its neighbors. Any neighbor without a copy gets one and joins the queue. Then the copy of the current node gets the copy of that neighbor appended to its list. Because neighbors are visited in the original order, every copied list keeps that order.
A node joins the queue exactly when its copy is made, so each node is queued once. Each edge is looked at twice, once from each end, which gives O(V + E). A depth-first search with the same dictionary also works.
Step by step
- Unwrap the argument with
guard let node = node elseand returnnil. An empty graph has nothing to copy, and the next lines read the node's value. After the guard,nodeis a plainNode. - Create
copiesas an empty[Node: Node]dictionary, avar. It maps each original node to its copy. - Copy node 1:
copies[node] = Node(node.val). The dictionary both finds the copy of any node met so far and tells which nodes have been met. - Create
queueholding justnode. Every node in it has a copy, but the copy's neighbor list is still empty. - Create
headat 0, the index of the next node to take. Moving an index forward is cheaper thanremoveFirst(), which shifts every remaining element. - Loop while
head < queue.count. - Take
queue[head]intocurrent. - Add 1 to
head. - Loop over
current.neighbors. - Check
copies[neighbor] == nil. A dictionary lookup returns an optional,nilfor a missing key. No copy means the search is meeting this node for the first time. - Make its copy with
Node(neighbor.val). - Append
neighbortoqueueso that its own neighbors are copied later. - Link the copies: append
copies[neighbor]!tocopies[current]!.neighbors. The copy ofcurrentpoints to the copy ofneighbor, never toneighboritself. - Return
copies[node], the copy of node 1.
The solution in Swift
class Solution {
func cloneGraph(_ node: Node?) -> Node? {
guard let node = node else {
return nil
}
var copies = [Node: Node]()
copies[node] = Node(node.val)
var queue = [node]
var head = 0
while head < queue.count {
let current = queue[head]
head += 1
for neighbor in current.neighbors {
if copies[neighbor] == nil {
copies[neighbor] = Node(neighbor.val)
queue.append(neighbor)
}
copies[current]!.neighbors.append(copies[neighbor]!)
}
}
return copies[node]
}
}
The Swift details worth a closer look:
- Classes are reference types.
Nodeis a class, so assigning a node to another variable shares it instead of copying it. That is why a real copy needsNode(neighbor.val)for each node. Copying the reference would leave the new graph pointing into the old one. - Hashable keys. A dictionary key must be
Hashable. Without that conformance,[Node: Node]fails to compile withtype 'Node' does not conform to protocol 'Hashable'. The lesson's class is hashable by identity, so each object is its own key. - Optional lookups.
copies[neighbor]has typeNode?. Comparing it withnilasks whether the key is missing. The!incopies[current]!andcopies[neighbor]!unwraps a value that is certain to exist by then, and would crash if it didn't. - Mutating through the dictionary.
copies[current]!.neighbors.append(...)works becauseNodeis a class: the unwrapped value is a reference to the same copy stored in the dictionary, so the change is kept. - The guard shadows the parameter.
guard let node = nodemakes a non-optionalnodethat hides the optional one for the rest of the method.
Complexity
Time: O(V + E). Each node is made and queued once. Each node's neighbor list is walked once, and the sum of the list lengths is 2E, since every edge appears in two lists. Dictionary operations take constant time on average.
Space: O(V) extra. The dictionary and the queue each hold up to V nodes. The new graph itself, with its neighbor lists, is the output.
Edge cases and common mistakes
- Empty graph. For
[]the function getsnil, the guard returnsnil, and nothing else runs. - A single node. For
[[]]the loop runs once with no neighbors, and the result is one new node with the value 1 and an empty list. - Cycles. In the square, nodes 1 and 2 are neighbors of each other. The dictionary check stops the search from copying node 1 a second time.
- Returning the original. Returning
nodewould pass an unchanged graph. In the test runs below, the copy of each graph shares no node with the original. - Linking to originals. Appending
neighborinstead ofcopies[neighbor]!to the new list makes the copy point into the original graph. - Keeping the order. Neighbors are appended in the original order, so
[[3, 2], [1], [1]]is copied with node 1's neighbors still in the order 3, 2. - Queueing late. Putting a node in the queue without making its copy first, or making the copy at the wrong time, can create two copies of one node.
Testing
Each graph below was copied and its adjacency lists read back from the copy. In every case the copy had the right number of nodes and shared none with the original.
[[2, 4], [1, 3], [2, 4], [1, 3]]gives[[2, 4], [1, 3], [2, 4], [1, 3]], with 4 new nodes.[[]]gives[[]], with 1 new node.[]gives[].[[2], [1, 3], [2]](a path) gives[[2], [1, 3], [2]], with 3 new nodes.[[2, 3], [1, 3], [1, 2]](a triangle) gives[[2, 3], [1, 3], [1, 2]].[[3, 2], [1], [1]]gives[[3, 2], [1], [1]].
