LeetCode #133: Clone Graph

https://leetcode.com/problems/clone-graph/description/

The problem asks us to make a deep copy of a given undirected graph. We are given a node of the graph and we need to return a node of the cloned graph.

The solution to this problem involves performing a Depth First Search (DFS) on the original graph and creating a corresponding clone of each node as we visit them. We also make sure to keep track of the visited nodes and their corresponding clones in a dictionary to avoid cycles.

Here are the steps to solve this problem:

1. Define a class Node that represents a node in the graph. It should have a val attribute that stores the value of the node and a neighbors attribute that stores a list of the node’s neighbors.
2. Define a cloneGraph method that takes a node parameter, which represents the starting node of the original graph.
3. Initialize a visited dictionary that will store the visited nodes and their corresponding clones.
4. Check if the given node is None. If it is, return None.
5. Check if the given node has already been visited. If it has, return the clone of the node from the visited dictionary.
6. Create a clone_node with the val attribute of the node and an empty list for its neighbors.
7. Add the node and its corresponding clone_node to the visited dictionary.
8. Iterate through each neighbor of the node. For each neighbor, call the cloneGraph method recursively to get its clone and add it to the neighbors list of the clone_node.
9. Return the clone_node.

Here is the code for the solution:

class Solution(object):

    def __init__(self):
        # Dictionary to save the visited node and it's respective clone
        # as key and value respectively. This helps to avoid cycles.
        self.visited = {}

    def cloneGraph(self, node):
        if not node:
            return node

        # If the node was already visited before.
        # Return the clone from the visited dictionary.
        if node in self.visited:
            return self.visited[node]

        # Create a clone for the given node.
        # Note that we don't have cloned neighbors as of now, hence [].
        clone_node = Node(node.val, [])

        # The key is original node and value being the clone node.
        self.visited[node] = clone_node

        # Iterate through the neighbors to generate their clones
        # and prepare a list of cloned neighbors to be added to the cloned node.
        if node.neighbors:
            clone_node.neighbors = [self.cloneGraph(n) for n in node.neighbors]

        return clone_node

Time and Space Complexity

The time complexity of this solution is O(N), where N is the number of nodes in the graph. We need to visit each node exactly once, and for each node, we need to visit all its neighbors once to create the clone. The space complexity of the solution is also O(N), since we need to store a clone of each node in the visited dictionary.