133 — Clone Graph
Restating Info We’re Already Given:
- We are given a node reference
- Must return a deep copy of the graph (cannot point to same references as original objects)
- Graph is represented as an adjacency list
Questions/Clarifications to Possibly Ask Interviewer (If starting information we’re given isn’t sufficient to begin):
- Is neighbors a list of Nodes (type Node)?
- What should we do when there is an empty adjacency list?
- What should we do if there is a node but it has no neighbors?
Discuss Solution #1:
To start, we need to store all the new nodes we create for the deep copy. To locate them in constant time, we can use a dictionary where the key-value pair is the node’s value and the node itself respectively. We can also have a visited set to determine in constant time whether or not we’ve already visited a node. For each node popped off of toVisit, we check if it’s in visited first. If not, add it into visited and for each neighbor(s) of the current node, we append the edge by appending to the current node’s neighbors. Then, we can add the neighbor to a toVisit queue to later be processed.
Discuss Optimal Solution:
The seen set can take up a lot of space if we have to deep copy a graph with many nodes, linear to the number of nodes. To make the solution better, we should only append nodes to the toVisit queue if we haven’t made an entry for it in our nodes dictionary because only these nodes have not been processed yet. As seen in the for loop, we add the edge for each neighbor for our current node. Thus, there’s no need to revisit a neighbor if it is already in the nodes dictionary as to be in the nodes dictionary we have already processed its neighbors or are currently doing so. This eliminates the need for the seen set and saves us space.
Code Optimal Solution:
Runtime/Space Complexity:
The optimal solution has a runtime complexity linear to the number of total edges in the graph as we have to recreate the entire graph and its edges. The space complexity linear to the number of nodes as we have to store all the nodes.
Test Cases:
- No node, empty adjacency list
- One node, no neighbors
- One node, one neighbor
- One node, many neighbors
- Many nodes, many neighbors
