clone graph

clone graph

DFS I like

I resolved a lot of problems in leetcode using DFS, which is my favourite. Using a map to record the pair of (label,UndirectedGraphNode*), which means whether we have created a node of label x or not. DFS originNode, if there is a newNode in map and the newNode has the same label with the originNode, return the pointer. Otherwise, create a new node, put it into map and DFS to create the neighbor with it using the originNode's neighbor list.

 1 /**
 2  * Definition for undirected graph.
 3  * struct UndirectedGraphNode {
 4  *     int label;
 5  *     vector<UndirectedGraphNode *> neighbors;
 6  *     UndirectedGraphNode(int x) : label(x) {};
 7  * };
 8  */
 9 class Solution {
10 private:
11 map < int, UndirectedGraphNode* > visited;
12 public:
13     UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
14         visited.clear();
15         return DFS(node);
16     }
17     UndirectedGraphNode *DFS( UndirectedGraphNode *originNode ) {
18         if ( !originNode ) {
19             return NULL;
20         }
21         if ( visited.find(originNode->label) != visited.end() ) {
22             return visited[originNode->label];
23         }
24         UndirectedGraphNode* newNode = new UndirectedGraphNode(originNode->label);
25         visited[originNode->label] = newNode;
26         for ( auto i = originNode->neighbors.begin(); i != originNode->neighbors.end(); i++ ) {
27             newNode->neighbors.push_back(DFS(*i));
28         }
29         return newNode;
30     }
31 };

Loading Disqus comments...
Table of Contents