133. Clone Graph

这道题目的意思是：对一个无向图进行深拷贝，即需要申请一个新的空间，并将原来的无向图中的节点及相关信息拷贝到这个新的空间。因此解题思路其实就是对这个无向图进行遍历，并且一边遍历一边深拷贝即可。对于无向图的遍历，可以采用深度遍历（DFS）和广度遍历（BFS）完成，两者的时间复杂度和空间复杂度都是O(n)。

方法一：深度遍历（DFS）

// Definition for undirected graph. struct UndirectedGraphNode { int label; vector<UndirectedGraphNode *> neighbors; UndirectedGraphNode(int x) : label(x) {}; }; class Solution { public: // Deep-First-Search (DFS) UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { if (node == NULL) return NULL; // key is original node, value is the copied node unordered_map<const UndirectedGraphNode *, UndirectedGraphNode *> copy; Clone(node, copy); return copy[node]; } private: static UndirectedGraphNode* Clone(const UndirectedGraphNode* node, unordered_map<const UndirectedGraphNode*, UndirectedGraphNode *> ©) { // a copy existed if (copy.find(node) != copy.end()) return copy[node]; // copy a node UndirectedGraphNode *newNode = new UndirectedGraphNode(node->label); copy[node] = newNode; for (auto nbptr : node->neighbors) newNode->neighbors.push_back(Clone(nbptr, copied)); return newNode; } };

方法二：广度遍历（BFS）

// Definition for undirected graph. struct UndirectedGraphNode { int label; vector<UndirectedGraphNode *> neighbors; UndirectedGraphNode(int x) : label(x) {}; }; class Solution { public: // BFS UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { if (node == NULL) return NULL; // key is original node, value is the copied node unordered_map<const UndirectedGraphNode *, UndirectedGraphNode *> copied; // each node in queue is copied itself but neighbours are not queue<const UndirectedGraphNode*> q; q.push(node); copied[node] = new UndirectedGraphNode(node->label); while (!q.empty()) { const UndirectedGraphNode* cur = q.front(); q.pop(); for (auto nbptr : cur->neighbors) { // a copy is existed if (copied.find(nbptr) != copied.end()) { copied[cur]->neighbors.push_back(copied[nbptr]); } else { UndirectedGraphNode* newNode = new UndirectedGraphNode(nbptr->label); copied[nbptr] = newNode; copied[cur]->neighbors.push_back(newNode); q.push(nbptr); } } } return copied[node]; } };