这期内容当中小编将会给大家带来有关C++中怎么利用LeetCode克隆无向图,文章内容丰富且以专业的角度为大家分析和叙述,阅读完这篇文章希望大家可以有所收获。
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:
The number of nodes will be between 1 and 100.
The undirected graph is a simple graph, which means no repeated edges and no self-loops in the graph.
Since the graph is undirected, if node p has node q as neighbor, then node q must have node p as neighbor too.
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克隆无向图了,如果刚好有类似的疑惑,不妨参照上述分析进行理解。如果想知道更多相关知识,欢迎关注亿速云行业资讯频道。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。