變量unordered_map
因為會有環,所以需要cloneMap記錄舊的節點和新的節點對。
還需要一個visited記錄已經訪問過的節點,可以和cloneMap合並在一起。
DFS:
在克隆某個Node時,首先放入map中。
之後遍歷neighbors。如果neighbors不在map裡,即沒有訪問過,則遞歸調用cloneGraph函數。
最後返回克隆過的節點。
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { if (node == NULL) return NULL; if (cloneMap.find(node) != cloneMap.end()) return cloneMap[node]; cloneMap[node] = new UndirectedGraphNode(node->label); cloneMap[node]->neighbors = vector(); for (int i = 0; i < node->neighbors.size(); i++) { UndirectedGraphNode * curNode = node->neighbors[i]; UndirectedGraphNode * newNode = cloneGraph(curNode); cloneMap[node]->neighbors.push_back(newNode); } return cloneMap[node]; }
BFS:
使用一個queue記錄要訪問的節點。
因為不能在訪問queue中節點的時候再創建對應的node==>因為在處理父親節點的時候需同時創建好其neighbors
所以需要在將不在map中的neighbors(沒有訪問過的子節點)放入queue的同時創建克隆的節點,並且放入map裡。
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { if (node == NULL) return NULL; vectorqueue; queue.push_back(node); cloneMap[node] = new UndirectedGraphNode(node->label); cloneMap[node]->neighbors = vector (); for (int i = 0; i < queue.size(); i++) { UndirectedGraphNode * newNode = cloneMap[queue[i]]; for (int j = 0; j < queue[i]->neighbors.size(); j++) { UndirectedGraphNode * curNb = queue[i]->neighbors[j]; if (cloneMap.find(curNb) == cloneMap.end()) { queue.push_back(curNb); UndirectedGraphNode * newNb = new UndirectedGraphNode(curNb->label); newNb->neighbors = vector (); cloneMap[curNb] = newNb; } newNode->neighbors.push_back(cloneMap[curNb]); } } return cloneMap[node]; }