Problem overview
The function cloneGraph gets node, node 1 of a connected, undirected graph, and returns a deep copy of the graph: the copy of node 1. The lesson provides the node type, shown in the starter code as a comment: a Node struct with an int field Val and a field Neighbors, a slice of *Node.
The graph has n nodes, numbered 1 to n, and node i has the value i. A deep copy is made of exactly n brand-new nodes with the same values, and 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. For an empty graph the function gets nil and returns nil.
In the first example the adjacency lists are [[2, 4], [1, 3], [2, 4], [1, 3]]: a square of four nodes, 1-2, 2-3, 3-4 and 4-1. The copy has four new nodes joined in the same shape. In the second example the graph is a single node with no neighbors, and the copy is one new node with the value 1.
The lesson 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: a map from each original to its copy
Copying one node is easy: make a Node with the same Val. The hard part is the neighbors. A copy's neighbor list must point to copies, never to originals, and a node can be reached from several others. The graph also has cycles, as in the square, so walking blindly from neighbor to neighbor never ends.
One map solves both problems. It maps each original node to its copy, and it does two jobs:
- It finds the copy of any node met so far, so a node is never copied twice.
- It tells which nodes have been met already, which stops the search from going around a cycle forever.
The search is a breadth-first search. A node's copy is made the first time the search meets the node, and that is also when the node joins the queue. When a node leaves the queue, the copies of its neighbors are appended to its copy's list. A recursive DFS with the same map works too; this lesson uses a BFS with its own queue.
Step by step
- Handle the empty graph. If
node == nil, returnnil. The next lines read the node's value, which needs a node. - Create the map
copieswithmake(map[*Node]*Node). The keys are pointers, so two different nodes are two different keys, even if their values were equal. - Add the first entry:
copies[node] = &Node{Val: node.Val}. The expression makes a new node and gives its address. ItsNeighborsstarts as an empty (nil) slice. - Create the queue as a slice of
*Nodeholding justnode. Every node in the queue already has its copy. What its copy lacks is the neighbor list, which is filled when the node leaves the queue. - Loop while
len(queue) > 0. The search ends when every reachable node has left the queue. - Take the first node:
current := queue[0], thenqueue = queue[1:]drops it. - Loop over
current.Neighborswithrange. Over the whole run each edge is looked at twice, once from each end, which is why the work isO(V + E). - Check
copies[neighbor] == nil. Reading a key that isn't in a map gives the zero value, which isnilfor a pointer. So no copy yet means the search is meeting this node for the first time. - Make the copy:
copies[neighbor] = &Node{Val: neighbor.Val}. A node that has a copy never gets a second one. - Queue it:
queue = append(queue, neighbor). A node joins the queue only when its copy is made, so each node is queued exactly once. - Link the copies after the
if, still inside the loop: appendcopies[neighbor]tocopies[current].Neighborsand store the result back. The copy ofcurrentpoints to the copy ofneighbor, never toneighboritself, and the neighbors come incurrent's order, so every copied list keeps the original order. - Return
copies[node], the copy of node 1.
The solution in Go
func cloneGraph(node *Node) *Node {
if node == nil {
return nil
}
copies := make(map[*Node]*Node)
copies[node] = &Node{Val: node.Val}
queue := []*Node{node}
for len(queue) > 0 {
current := queue[0]
queue = queue[1:]
for _, neighbor := range current.Neighbors {
if copies[neighbor] == nil {
copies[neighbor] = &Node{Val: neighbor.Val}
queue = append(queue, neighbor)
}
copies[current].Neighbors = append(copies[current].Neighbors, copies[neighbor])
}
}
return copies[node]
}
The Go details worth a closer look:
- Composite literals and pointers.
&Node{Val: node.Val}builds a struct and takes its address in one expression. Fields not named, such asNeighbors, start with their zero value, here a nil slice. - Pointer keys. A
map[*Node]*Nodecompares keys by address. Two nodes with the sameValbut different addresses are different keys, which is what this problem needs. - Missing keys give the zero value.
copies[neighbor] == nilworks as a "not seen yet" test because every stored value is a non-nil pointer. For other value types you would usev, ok := m[k]. appendreturns the slice. It may allocate a new array, so the result is assigned back tocopies[current].Neighbors. Becausecopies[current]is a pointer, the assignment changes the copy itself.queue = queue[1:]is the slice without its first element. It is a simple queue for this lesson.
Complexity
Time: O(V + E). Every node is queued once, and every neighbor list is read once. The map operations take constant time on average.
Space: O(V) extra. The map holds one entry per node, and the queue never holds more than V nodes. The new neighbor lists are part of the copy itself, not extra space.
Edge cases and common mistakes
- An empty graph.
nilin,nilout. Without the first check,node.Valwould stop the program with a nil pointer dereference. - A single node. The queue holds it once, its neighbor loop does nothing, and the copy has an empty neighbor list.
- Linking to originals. Appending
neighborinstead ofcopies[neighbor]makes a copy that still points into the original graph. The shallow version&Node{Val: node.Val, Neighbors: node.Neighbors}has the same problem: its first neighbor is the very same node as the original's. - Copying a node twice. If you make a copy without first checking the map, the same original gets several copies, and the graph's shape breaks.
- No map, no stop. Without a record of the met nodes, a cycle such as the square sends the search around forever.
Testing
These are the adjacency lists of the copy the function returns, read node by node from node 1, for each graph:
[[2, 4], [1, 3], [2, 4], [1, 3]]gives[[2 4] [1 3] [2 4] [1 3]], with 4 nodes and none shared with the original.[[]]gives[[]]: one node, no neighbors.[]givesnil.[[2, 3], [1, 3], [1, 2]], a triangle, gives[[2 3] [1 3] [1 2]].[[2], [1, 3], [2]], a path of three nodes, gives[[2] [1 3] [2]].
On the square, the search queues the nodes in the order 1, 2, 4, 3: node 1's neighbors are 2 and 4, and node 3 is first met from node 2.
