C++中怎么利用LeetCode克隆無向圖

這期內容當中小編將會給大家帶來有關C++中怎么利用LeetCode克隆無向圖，文章內容豐富且以專業的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

[LeetCode] 133. Clone Graph 克隆無向圖

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.

Example:

Input:
{"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1}

Explanation:
Node 1's value is 1, and it has two neighbors: Node 2 and 4.
Node 2's value is 2, and it has two neighbors: Node 1 and 3.
Node 3's value is 3, and it has two neighbors: Node 2 and 4.
Node 4's value is 4, and it has two neighbors: Node 1 and 3.

Note:

1. The number of nodes will be between 1 and 100.

2. The undirected graph is a simple graph, which means no repeated edges and no self-loops in the graph.

3. Since the graph is undirected, if node p has node q as neighbor, then node q must have node p as neighbor too.

4. You must return the copy of the given node as a reference to the cloned graph.

這道無向圖的復制問題和之前的 Copy List with Random Pointer 有些類似，那道題的難點是如何處理每個結點的隨機指針，這道題目的難點在于如何處理每個結點的 neighbors，由于在深度拷貝每一個結點后，還要將其所有 neighbors 放到一個 vector 中，而如何避免重復拷貝呢？這道題好就好在所有結點值不同，所以我們可以使用 HashMap 來對應原圖中的結點和新生成的克隆圖中的結點。對于圖的遍歷的兩大基本方法是深度優先搜索 DFS 和廣度優先搜索 BFS，這里我們先使用深度優先搜索DFS來解答此題，在遞歸函數中，首先判空，然后再看當前的結點是否已經被克隆過了，若在 HashMap 中存在，則直接返回其映射結點。否則就克隆當前結點，并在 HashMap 中建立映射，然后遍歷當前結點的所有 neihbor 結點，調用遞歸函數并且加到克隆結點的 neighbors 數組中即可，代碼如下：

解法一：

class Solution {
public:
    Node* cloneGraph(Node* node) {
        unordered_map<Node*, Node*> m;
        return helper(node, m);
    }
    Node* helper(Node* node, unordered_map<Node*, Node*>& m) {
        if (!node) return NULL;
        if (m.count(node)) return m[node];
        Node *clone = new Node(node->val);
        m[node] = clone;
        for (Node *neighbor : node->neighbors) {
            clone->neighbors.push_back(helper(neighbor, m));
        }
        return clone;
    }
};

我們也可以使用 BFS 來遍歷圖，使用隊列 queue 進行輔助，還是需要一個 HashMap 來建立原圖結點和克隆結點之間的映射。先克隆當前結點，然后建立映射，并加入 queue 中，進行 while 循環。在循環中，取出隊首結點，遍歷其所有 neighbor 結點，若不在 HashMap 中，我們根據 neigbor 結點值克隆一個新 neighbor 結點，建立映射，并且排入 queue 中。然后將 neighbor 結點在 HashMap 中的映射結點加入到克隆結點的 neighbors 數組中即可，參見代碼如下：

解法二：

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (!node) return NULL;
        unordered_map<Node*, Node*> m;
        queue<Node*> q{{node}};
        Node *clone = new Node(node->val);
        m[node] = clone;
        while (!q.empty()) {
            Node *t = q.front(); q.pop();
            for (Node *neighbor : t->neighbors) {
                if (!m.count(neighbor)) {
                    m[neighbor] = new Node(neighbor->val);
                    q.push(neighbor);
                }
                m[t]->neighbors.push_back(m[neighbor]);
            }
        }
        return clone;
    }
};

上述就是小編為大家分享的C++中怎么利用LeetCode克隆無向圖了，如果剛好有類似的疑惑，不妨參照上述分析進行理解。如果想知道更多相關知識，歡迎關注億速云行業資訊頻道。