C++实现LeetCode(133.克隆无向图)

这篇文章主要介绍了C++实现LeetCode(133.克隆无向图),本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下

C++实现LeetCode(133.克隆无向图),久久派带你了解更多相关信息。

[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:

C++实现LeetCode(133.克隆无向图)

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;    }};

类似题目:

Copy List with Random Pointer

参考资料:

https://leetcode.com/problems/clone-graph/

https://leetcode.com/problems/clone-graph/discuss/42313/C%2B%2B-BFSDFS

https://leetcode.com/problems/clone-graph/discuss/42309/Depth-First-Simple-Java-Solution

到此这篇关于C++实现LeetCode(133.克隆无向图)的文章就介绍到这了,更多相关C++实现克隆无向图内容请搜索趣讯吧以前的文章或继续浏览下面的相关文章希望大家以后多多支持趣讯吧!

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,请发送邮件至 203304862@qq.com 举报,一经查实,本站将立刻删除。转转请注明出处:https://www.szhjjp.com/n/7248.html

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注