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 *> &copy) {
        // 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];
    }
};