Leetcode: Clone Graph

Leetcode: Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ’s undirected graph serialization: Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node. As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2. Second node is labeled as 1. Connect node 1 to node 2. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle. Visually, the graph looks like the following:

1 / \ / \0 --- 2 / \ \_/

题目要求克隆图，采用深度优先或者广度优先进行遍历。使用一个Map存储原始节点和克隆以后的节点。

参考代码（使用深度优先遍历）：

/** * Definition for undirected graph. * struct UndirectedGraphNode { * int label; * vector neighbors; * UndirectedGraphNode(int x) : label(x) {}; * }; */class Solution {public: UndirectedGraphNode* cloneGraph(UndirectedGraphNode* node) { if (node == nullptr) return nullptr; // map的key为原始节点，value为拷贝的节点 unordered_map copyMap; // 完成给定节点的图的拷贝工作 clone(node, copyMap); return copyMap[node]; }private: static UndirectedGraphNode* clone(UndirectedGraphNode* node, unordered_map ©Map) { // 如果该节点已经拷贝过，直接返回该节点的拷贝 if (copyMap.find(node) != copyMap.end()) return copyMap[node]; // 否则，拷贝该节点及其相邻节点 UndirectedGraphNode* copiedNode = new UndirectedGraphNode(node->label); copyMap[node] = copiedNode; for (auto neighborNode : node->neighbors) copiedNode->neighbors.push_back(clone(neighborNode, copyMap)); return

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。