📊133. Clone Graph
Medium | Grind 75 | July 12 2022
Given a reference of a node in a connected undirected graph.
Return a deep copy (clone) of the graph.
Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.
class Node {
public int val;
public List<Node> neighbors;
}Test case format:
For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.
An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.
The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.
Constraints:
The number of nodes in the graph is in the range
[0, 100].1 <= Node.val <= 100Node.valis unique for each node.There are no repeated edges and no self-loops in the graph.
The Graph is connected and all nodes can be visited starting from the given node.
Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
SOLUTION
The main task here is to traverse the graph and at each node, create new nodes since we need to make deep copy. Deep copy has to store the objects actual value where as shallow copy we basically store the referenceof objects to the original memory (geeksforgeeks).
There are two ways to solve this problem. Breath First Search (BFS) vs Depth First Search (DFS). When I solved this initially, I used DFS since that was more intuitive for me. However, after exploring a solution using BFS, that was much nicer and easier since it can be done iteratively.
1. DEPTH FIRST SEARCH
For the following solution, we will first look at the first node. We make a copy of that node and look at the neighbors. When we look at the neighbors we take the first neighbors and recusively go through its neighbor and its neighbor and so on.
Example 1: In the above example, we will first look at node 1. Once we create node 1 and store in our output dictionary, we will move to its neighbor. When look at the neighbor, we will first encounter 2. Before we can process neighbor 4, we have go down the rabbit hole of node 2. We look at the neighbor of node 2 which is 1 and 3. We will encounter Node 1 first, but since we saw node 1 already, we return and we will now look at node 3. We create a new node with value 3 and iterate over its neighbors which are 2 and 4. We first look at Node 2, and since we saw it earlier, we return. We now move to Node 4. We create a new Node with value 4 and look at its neighbors which are 1 and 3. since we already saw them, we return. this can triggers the return each recursive calls since we have seen and copied all the nodes.
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
if node:
visited = {} #store all the visited values/nodes since every value is unique.
output = {} # dictionary to store the deep copied nodes.
result = self.create_nodes(visited, node, output)
return result[1] # the value of the first node is always 1. return the first node
return node
def create_nodes(self,visited, node, output):
'''
recusively calls itself until it has been called with every node as arguments
parameter:
1. visited: dictionary containg integer values. track visited nodes
2. node: the current node we are looking at
3. output: dictionary containing all the newly created nodes.
return:
output; dictionary with all the copied nodes
'''
if node.val in visited: # have we seen the node before?
return
visited[node.val] = 1 # we have seen this node now.
# create a new node with the same value as the node. DEEP COPY
if node.val not in output:
output[node.val] = Node(node.val)
# iterate through its neighbor.
for neighbor in node.neighbors:
# if we are seeing this neighbor node for the first time, create a new node.
if neighbor.val not in output:
output[neighbor.val] = Node(neighbor.val)
output[node.val].neighbors.append(output[neighbor.val])
# go down the neighbors basically DFS
self.create_nodes(visited, neighbor, output)
return outputpython2. BREATH FIRST SEARCH
The workings of BFS is similar to DPS but here we look at each level at a time. Instead of going through the rabbit hole of a neighbor, then the neighbor of the neighbor and again its neighbor, in BFS, we will tackle all the neighbors of the first node. Then move to the next node and tackle all its neighbors.
For the solution below, we will use a dictionary to store the newly created nodes and an array acting like a queue to contain the nodes that needs to be processed. We append the first node to our queue so that our queue is not empty. Then we get into the loop and pop the first node. we create a new node with the corresponding value and iterate over its neighbors. If we are seeing the neighbors for the first time, we create a new Node with their corresponding value and then add them to the queue so they can be processed. Processed here basically means append appropiate neighbors for the node.
This process will methodically go through the graph level wise. In example 1, the queue will first process Node 1. While processing this it will add Node 2 and Node 4 to the queue. It then prcoesses Node 2 and then Node 4. When processing Node 2, Node 3 will be added to the queue. However, Node 3 wont be processed until we have finished processed Node 4 since that was seen first.
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
if node:
output = {} # dictionary to store the deep copied nodes.
queue = [] # store the nodes to be processed
queue.append(node) # append the first node so that it is not empty to begin with.
while queue: # the loop goes on until out queue is empty. This mean we have seen all the nodes
current_node = queue.pop(0) # pop the first node
if current_node.val not in output: # create a new node with the value of the original node
output[current_node.val] = Node(current_node.val)
for neigh in current_node.neighbors: # iterate over all the neighbors
if neigh.val not in output:# deep copy each neighbor nodes
output[neigh.val] = Node(neigh.val)
queue.append(neigh) # append to the queue if neighbor node is seen for the first time.
# append the newly created neighbor nodes as the neighbor of the current node
output[current_node.val].neighbors.append(output[neigh.val])
return output[1] # the value of the first node is always 1. return the first node
return
TIME AND SPACE COMPLEXITY Time complexity: For both DFS and BFS, we go through every single node once in the graph, so therefore the time complexity is O(v + e) where v is the number of vertices and e is the edges.
Space Complexity: For Both DFS and BFS, we use a dictionary to hold all the nodes. The size of the dictionary is the number of nodes since we have to store all the unique nodes in it. Therefore the space complexity is O(v) where v is the number of nodes
Last updated