Clone Graph
Clarify the problem:
- The problem requires us to clone an undirected graph.
- The graph is represented using an adjacency list, where each node in the graph is a Node object with a unique value and a list of neighbors.
- We need to implement a function that takes the reference to a node in the original graph and returns a deep copy of the graph.
Analyze the problem:
- Input: A reference to a node in the original graph.
- Output: A deep copy of the graph.
- Constraints:
- The graph is an undirected graph.
- The graph is represented using an adjacency list.
- Each node in the graph has a unique value.
Design an algorithm:
- We can use depth-first search (DFS) to traverse the graph and create a deep copy.
- Create an empty dictionary to store the mapping between original nodes and their clones.
- Implement a recursive helper function,
dfs
, that takes a node in the original graph as input:- Create a clone of the current node and add it to the dictionary.
- Iterate through the neighbors of the current node:
- If the neighbor is already in the dictionary, add its clone to the clone's neighbors.
- Otherwise, recursively call the
dfs
function on the neighbor and add its clone to the clone's neighbors.
- Call the
dfs
function on the input node to start the DFS traversal. - Return the clone of the input node.
Explain your approach:
- We will implement a function called
cloneGraph
to solve the problem. - The function will take a node in the original graph as input.
- We will create an empty dictionary to store the mapping between original nodes and their clones.
- We will use a recursive helper function,
dfs
, to perform the DFS traversal and create the deep copy of the graph. - The
dfs
function will create a clone of each node encountered and add it to the dictionary. - For each neighbor of a node, if the neighbor is already in the dictionary, we add its clone to the clone's neighbors. Otherwise, we recursively call the
dfs
function on the neighbor and add its clone to the clone's neighbors. - Finally, we call the
dfs
function on the input node and return its clone.
- We will implement a function called
Write clean and readable code:
pythonclass Node: def __init__(self, val=0, neighbors=None): self.val = val self.neighbors = neighbors if neighbors is not None else [] def cloneGraph(node): if not node: return None clone_dict = {} def dfs(node): clone = Node(node.val) clone_dict[node] = clone for neighbor in node.neighbors: if neighbor in clone_dict: clone.neighbors.append(clone_dict[neighbor]) else: clone.neighbors.append(dfs(neighbor)) return clone return dfs(node)
Test your code:
- To test the code, we need to create a graph and verify that the cloned graph is correct.
- Let's create a graph with the following structure:lua
1 -- 2 | | 4 -- 3
- We will use the node with value 1 as the input to the
cloneGraph
function and compare the cloned graph with the original graph. # Create the original graph node1 = Node(1) node2 = Node(2) node3 = Node(3) node4 = Node(4) node1.neighbors = [node2, node4] node2.neighbors = [node1, node3] node3.neighbors = [node2, node4] node4.neighbors = [node1, node3] # Clone the graph clone = cloneGraph(node1) # Check if the cloned graph is correct assert clone.val == 1 assert clone.neighbors[0].val == 2 assert clone.neighbors[1].val == 4 assert clone.neighbors[0].neighbors[0].val == 1 assert clone.neighbors[0].neighbors[1].val == 3 assert clone.neighbors[1].neighbors[0].val == 1 assert clone.neighbors[1].neighbors[1].val == 3 assert clone.neighbors[0].neighbors[0] is clone assert clone.neighbors[1].neighbors[0] is clone assert clone.neighbors[0].neighbors[1] is clone.neighbors[1] assert clone.neighbors[1].neighbors[1] is clone.neighbors[0]
We have tested the code with a sample graph and verified that the cloned graph matches the original graph.
Optimize if necessary:
- The current solution has a time complexity of O(N), where N is the total number of nodes in the graph.
- This is because we perform a DFS traversal to visit each node exactly once.
- The space complexity is also O(N) because we use a dictionary to store the mapping between original nodes and their clones.
Handle error cases:
- The code assumes that the input node is not None.
- If the input node is None, the function returns None as well.
- The code does not explicitly handle other error cases, such as invalid input or cyclic graphs. Handling such cases can be added as needed.
Discuss complexity analysis:
- Let N be the total number of nodes in the graph.
- The time complexity of the solution is O(N) because we perform a DFS traversal to visit each node exactly once.
- The space complexity is also O(N) because we use a dictionary to store the mapping between original nodes and their clones.
python