{"id":2461,"date":"2024-03-16T13:00:00","date_gmt":"2024-03-16T13:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=2461"},"modified":"2024-03-19T09:19:43","modified_gmt":"2024-03-19T09:19:43","slug":"clone-graph-problem","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/clone-graph-problem\/","title":{"rendered":"Clone Graph Problem Solved ( C++, Java Python)"},"content":{"rendered":"\n

The undirected graph allows you to move in both directions of the edge, unlike the directed graph where you can only move in one direction which is specified. One interesting leetcode problem with undirected graphs is the Clone Graph Problem, which we will try to solve here!<\/p>\n\n\n\n

What is the Clone Graph Problem?<\/strong><\/h2>\n\n\n\n

In the Clone Graph problem, we are given an undirected connected graph. We have to clone this graph such that the new graph is a deep copy of the given graph. Deep Copy creates a new variable that stores the value of the previous variables. <\/strong><\/p>\n\n\n\n

Let\u2019s understand the Clone Graph problem with an example:<\/p>\n\n\n\n

\"Example<\/figure>\n\n\n\n

Note:<\/strong> All the values of nodes are distinct.<\/p>\n\n\n\n

Breath First Search Approach<\/strong><\/h2>\n\n\n\n

In the BFS approach using C++<\/a>, we will traverse the graph levels. We will create a queue that will help us to store the nodes in order of their levels. We will also use the hash map to check what are the neighbouring nodes of each node.\u00a0<\/p>\n\n\n\n

Here’s how we will do it for Clone Graph problem:<\/p>\n\n\n\n

    \n
  1. First create two maps, one to store neighboring nodes of each node and the other to store the new node address associated with the given value of the node.<\/li>\n\n\n\n
  2. Now create a queue and store the root node in it. Now call the loop till the size of the queue is greater than 0.<\/li>\n\n\n\n
  3. Create a new node that has a value the same as the front element of the queue. Store the address of this newly created node in the map.<\/li>\n\n\n\n
  4. Now check for all the neighboring elements of this node and store the values of each node in the newly created array. <\/li>\n\n\n\n
  5. Now iterate over all the newly created nodes call their neighbouring elements value and assign the nodes associated with that value to the neighboring nodes of the current node.<\/li>\n\n\n\n
  6. At last return the node with value 1.<\/li>\n<\/ol>\n\n\n\n

    The time complexity for the above process is O(m log (m)), where n is the total number of nodes in the graph. As we are doing BFS whose time complexity is O(n) and inserting the value into the map took O(n log(n)) time. So the overall time complexity will be O(n log(n)). The space complexity is O(n) storing the nodes in the map.\u00a0<\/p>\n\n\n\n

    Depth First Search Approach<\/strong><\/h2>\n\n\n\n

    The best way to solve the Clone Graph problem is by going to each node and copying the values of each node into a new node. We will start from the root node and keep on traversing the adjacent nodes till we reach the same elements again. We will use the map to store the visited nodes to check the repeated elements.<\/strong><\/p>\n\n\n\n

    In this DFS approach<\/a>, we will perform the following steps:<\/p>\n\n\n\n

      \n
    1. First, create a function DFS that will return the cloned graph. Pass the root of the given graph.<\/li>\n\n\n\n
    2. Now check the base condition, if the root node is NULL return NULL.<\/li>\n\n\n\n
    3. Create a new node and store the root node’s value in this. Also, mark the node value visited in the map.<\/li>\n\n\n\n
    4. Call all the nodes adjacent to the root node and check if they are previously visited or not. If they are previously visited push the node that was created earlier to the neighboring vector of the current root.<\/li>\n\n\n\n
    5. Otherwise, call the DFS function for this node and push the resultant node to the neighbouring vector of the current root.<\/li>\n\n\n\n
    6. Return the head of the new node.<\/li>\n<\/ol>\n\n\n\n

      Now, it’s time to implement it.<\/p>\n\n\n\n

      C++ Code<\/strong><\/h3>\n\n\n\n

      Here is the C++ solution for Clone Graph problem:<\/p>\n\n\n\n

      #include<bits\/stdc++.h>\nusing namespace std;\n\nclass Node {\npublic:\n    int val;\n    vector<Node*> neighbors;\n    Node() {\n        val = 0;\n        neighbors = vector<Node*>();\n    }\n    Node(int x) {\n        val = x;\n        neighbors = vector<Node*>();\n    }\n};\n\n\n    bool  vis[102];\n    Node* x[102];\n    Node* dp(Node* node){\n        if(node==NULL)return NULL;    \n        Node* head=new Node(node->val);\n        head->val=node->val;\n        x[head->val]=head;\n        vis[node->val]=true;\n        vector<Node *>v=node->neighbors;\n        vector<Node*>nw;\n        for(auto child:v){\n            if(vis[child->val])nw.push_back(x[child->val]);\n            else nw.push_back(dp(child));\n        }\n        head->neighbors=nw;\n        return x[head->val]=head;\n    }\n    \n    int main(){\n        Node* root1 = new Node(1);\n        Node* root2 = new Node(2);\n        Node* root3 = new Node(3);\n        Node* root4 = new Node(4);\n        \/\/ graph look like this\n        \/\/ 1 .... 2\n        \/\/ .      .\n        \/\/ .      .\n        \/\/ 4 .... 3\n        root1->neighbors.push_back(root2);\n        root1->neighbors.push_back(root4);\n        root2->neighbors.push_back(root1);\n        root2->neighbors.push_back(root3);\n        root3->neighbors.push_back(root2);\n        root3->neighbors.push_back(root4);\n        root4->neighbors.push_back(root1);\n        root4->neighbors.push_back(root3);\n\n        \/\/ calling function dp\n        Node* new_root = dp(root1);\n        \n        return 0;\n    }\n<\/pre><\/div>\n\n\n\n
      Java Code<\/strong><\/h3>\n\n\n\n
      We can also perform the DFS approach with Java:<\/p>\n\n\n\n
      import java.util.*;\n\nclass Node {\n\n\u00a0\u00a0\u00a0\u00a0int val;\n\n\u00a0\u00a0\u00a0\u00a0List<Node> neighbors;\n\n\u00a0\u00a0\u00a0\u00a0Node() {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0val = 0;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0neighbors = new ArrayList<>();\n\n\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0Node(int x) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0val = x;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0neighbors = new ArrayList<>();\n\n\u00a0\u00a0\u00a0\u00a0}\n\n}\n\nclass DeepCopyGraph {\n\n\u00a0\u00a0\u00a0\u00a0static boolean[] vis = new boolean[102];\n\n\u00a0\u00a0\u00a0\u00a0static Node[] x = new Node[102];\n\n\u00a0\u00a0\u00a0\u00a0static Node dp(Node node) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if (node == null) return null;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Node head = new Node(node.val);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0head.val = node.val;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0x[head.val] = head;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0vis[node.val] = true;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0List<Node> v = node.neighbors;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0List<Node> nw = new ArrayList<>();\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0for (Node child : v) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if (vis[child.val]) nw.add(x[child.val]);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0else nw.add(dp(child));\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0head.neighbors = nw;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0x[head.val] = head;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return x[head.val];\n\n\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0public static void main(String[] args) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Node root1 = new Node(1);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Node root2 = new Node(2);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Node root3 = new Node(3);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Node root4 = new Node(4);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\/\/ graph looks like this\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\/\/ 1 .... 2\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\/\/ .\u00a0 \u00a0 \u00a0 .\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\/\/ .\u00a0 \u00a0 \u00a0 .\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\/\/ 4 .... 3\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0root1.neighbors.add(root2);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0root1.neighbors.add(root4);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0root2.neighbors.add(root1);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0root2.neighbors.add(root3);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0root3.neighbors.add(root2);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0root3.neighbors.add(root4);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0root4.neighbors.add(root1);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0root4.neighbors.add(root3);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\/\/ calling function dp\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Node new_root = dp(root1);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\/\/ Your logic to work with new_root\n\n\u00a0\u00a0\u00a0\u00a0}\n\n}<\/pre><\/div>\n\n\n\n
      Python Code<\/strong><\/h3>\n\n\n\n
      Here is the Python program to clone an undirected graph:<\/p>\n\n\n\n
      class Node:\n\n\u00a0\u00a0\u00a0\u00a0def __init__(self, x):\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0self.val = x\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0self.neighbors = []\n\ndef dp(node, vis, x):\n\n\u00a0\u00a0\u00a0\u00a0if node is None:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return None\n\n\u00a0\u00a0\u00a0\u00a0head = Node(node.val)\n\n\u00a0\u00a0\u00a0\u00a0head.val = node.val\n\n\u00a0\u00a0\u00a0\u00a0x[head.val] = head\n\n\u00a0\u00a0\u00a0\u00a0vis[node.val] = True\n\n\u00a0\u00a0\u00a0\u00a0v = node.neighbors\n\n\u00a0\u00a0\u00a0\u00a0nw = []\n\n\u00a0\u00a0\u00a0\u00a0for child in v:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if vis[child.val]:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0nw.append(x[child.val])\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0else:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0nw.append(dp(child, vis, x))\n\n\u00a0\u00a0\u00a0\u00a0head.neighbors = nw\n\n\u00a0\u00a0\u00a0\u00a0x[head.val] = head\n\n\u00a0\u00a0\u00a0\u00a0return x[head.val]\n\nif __name__ == "__main__":\n\n\u00a0\u00a0\u00a0\u00a0vis = [False] * 102\n\n\u00a0\u00a0\u00a0\u00a0x = [None] * 102\n\n\u00a0\u00a0\u00a0\u00a0root1 = Node(1)\n\n\u00a0\u00a0\u00a0\u00a0root2 = Node(2)\n\n\u00a0\u00a0\u00a0\u00a0root3 = Node(3)\n\n\u00a0\u00a0\u00a0\u00a0root4 = Node(4)\n\n\u00a0\u00a0\u00a0\u00a0# graph looks like this\n\n\u00a0\u00a0\u00a0\u00a0# 1 .... 2\n\n\u00a0\u00a0\u00a0\u00a0# .\u00a0 \u00a0 \u00a0 .\n\n\u00a0\u00a0\u00a0\u00a0# .\u00a0 \u00a0 \u00a0 .\n\n\u00a0\u00a0\u00a0\u00a0# 4 .... 3\n\n\u00a0\u00a0\u00a0\u00a0root1.neighbors.extend([root2, root4])\n\n\u00a0\u00a0\u00a0\u00a0root2.neighbors.extend([root1, root3])\n\n\u00a0\u00a0\u00a0\u00a0root3.neighbors.extend([root2, root4])\n\n\u00a0\u00a0\u00a0\u00a0root4.neighbors.extend([root1, root3])\n\n\u00a0\u00a0\u00a0\u00a0# calling function dp\n\n\u00a0\u00a0\u00a0\u00a0new_root = dp(root1, vis, x)<\/pre><\/div>\n\n\n\n
      The time complexity to solve the Clone Graph problem using Depth-First search is O(n log (N)), where n is the total number of nodes in the graph. <\/strong>As we are doing DFS whose time complexity is O(n) and inserting the value into the map took O(n log(n)) time. So the overall time complexity will be O(n log(n)). <\/p>\n\n\n\n
      The space complexity is O(n) storing the nodes in the map.\u00a0A similar problem is to detect cycles in an indirect graph<\/a>, also to be solved using DFS.<\/p>\n\n\n\n
      Both the approaches have same time and space complexities:<\/p>\n\n\n\n
      Approach<\/th>Time Complexity<\/th>Space Complexity<\/th>Description<\/th><\/tr><\/thead>
      BFS Approach<\/td>O(N log(N))<\/td>O(N)<\/td>Traversing the BFS took O(N) time complexity and storing values in the map took log(N) complexity so the overall complexity will become O(N log(N)).<\/td><\/tr>
      DFS Approach<\/td>O(N log(N))<\/td>O(N)<\/td>Traversing the DFS took O(N) time complexity, and storing values in the map took log(N) complexity so the overall complexity will become O(N log(N)).<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
      Conclusion<\/strong><\/h2>\n\n\n\n
      In this post, we solved the Clone Graph Problem from leetcode<\/a>. We tried different approaches. One is BFS which does not use any extra stack space as it is an iterative approach, whereas the DFS approach takes extra stack space as it is the recursive approach. <\/p>\n","protected":false},"excerpt":{"rendered":"
      The undirected graph allows you to move in both directions of the edge, unlike the directed graph where you can only move in one direction which is specified. One interesting leetcode problem with undirected graphs is the Clone Graph Problem, which we will try to solve here! What is the Clone Graph Problem? In the […]<\/p>\n","protected":false},"author":14,"featured_media":2524,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[29,14,78,15],"class_list":["post-2461","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-bfs","tag-dsa","tag-graph","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/2461","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/14"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=2461"}],"version-history":[{"count":4,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/2461\/revisions"}],"predecessor-version":[{"id":2525,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/2461\/revisions\/2525"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/2524"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=2461"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=2461"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=2461"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}