Clone Graph## [更多技术博客 http://vilins.top/](http://vilins.top/)1. 题目Given the head of a graph, return a deep copy (clone) of the graph. Each node in the graph contains alabel(int) and a list (List[UndirectedGraphNode]) of itsneighbors. There is an edge between the given node and each of the nodes in its neighbors.OJs undirected graph serialization (so you can understand error output):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 as0. Connect node0to both nodes1and2.Second node is labeled as1. Connect node1to node2.Third node is labeled as2. Connect node2to node2(itself), thus forming a self-cycle.Visually, the graph looks like the following:1 / \ / \ 0 --- 2 / \ \_/Note: The information about the tree serialization is only meant so that you can understand error output if you get a wrong answer. You dont need to understand the serialization to solve the problem.2. 分析这题的数据结构题目已经明确给出我们可以看到这个数据结构就是树的递归定义节点的左子树和右子树也是一棵树。这里看起来像是需要递归的定义去实现其实不是通过树的类广度遍历与广度遍历有点差别可以同时遍历父节点和其子节点。这里的难点是发现未被访问的节点后如何同时定位到新链的同一个节点我们采取一个map的数据结构map旧节点新节点这样可以很好的解决这个问题。3. 源码struct UndirectedGraphNode { int label; vectorUndirectedGraphNode * neighbors; UndirectedGraphNode(int x) : label(x) {}; }; class Solution { public: UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { if(node NULL) { return NULL; } queueUndirectedGraphNode * q; setUndirectedGraphNode * s; UndirectedGraphNode *newGraph new UndirectedGraphNode(node-label); UndirectedGraphNode *resultGraph newGraph; //通过旧的点找到新图的点因为需要新图的连接 mapUndirectedGraphNode *, UndirectedGraphNode * m; q.push(node); s.insert(node); m[node] newGraph; while(!q.empty()) { //一层的顶点 int size q.size(); for(int i 0; i size; i) { UndirectedGraphNode *temp q.front(); UndirectedGraphNode *end m[temp]; q.pop(); for(int j 0; j temp-neighbors.size(); j) { if(s.find(temp-neighbors[j]) s.end()) { s.insert(temp-neighbors[j]); q.push(temp-neighbors[j]); } if(m.find(temp-neighbors[j]) m.end()) { UndirectedGraphNode* copiedNeighbor new UndirectedGraphNode(temp-neighbors[j]-label); m[temp-neighbors[j]] copiedNeighbor; } //将一个图接起来 end-neighbors.push_back(m[temp-neighbors[j]]); } } } return resultGraph; } };## [更多技术博客 http://vilins.top/](http://vilins.top/)
LeetCode--Clone Graph
发布时间：2026/6/2 11:59:53
Clone Graph## [更多技术博客 http://vilins.top/](http://vilins.top/)1. 题目Given the head of a graph, return a deep copy (clone) of the graph. Each node in the graph contains alabel(int) and a list (List[UndirectedGraphNode]) of itsneighbors. There is an edge between the given node and each of the nodes in its neighbors.OJs undirected graph serialization (so you can understand error output):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 as0. Connect node0to both nodes1and2.Second node is labeled as1. Connect node1to node2.Third node is labeled as2. Connect node2to node2(itself), thus forming a self-cycle.Visually, the graph looks like the following:1 / \ / \ 0 --- 2 / \ \_/Note: The information about the tree serialization is only meant so that you can understand error output if you get a wrong answer. You dont need to understand the serialization to solve the problem.2. 分析这题的数据结构题目已经明确给出我们可以看到这个数据结构就是树的递归定义节点的左子树和右子树也是一棵树。这里看起来像是需要递归的定义去实现其实不是通过树的类广度遍历与广度遍历有点差别可以同时遍历父节点和其子节点。这里的难点是发现未被访问的节点后如何同时定位到新链的同一个节点我们采取一个map的数据结构map旧节点新节点这样可以很好的解决这个问题。3. 源码struct UndirectedGraphNode { int label; vectorUndirectedGraphNode * neighbors; UndirectedGraphNode(int x) : label(x) {}; }; class Solution { public: UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { if(node NULL) { return NULL; } queueUndirectedGraphNode * q; setUndirectedGraphNode * s; UndirectedGraphNode *newGraph new UndirectedGraphNode(node-label); UndirectedGraphNode *resultGraph newGraph; //通过旧的点找到新图的点因为需要新图的连接 mapUndirectedGraphNode *, UndirectedGraphNode * m; q.push(node); s.insert(node); m[node] newGraph; while(!q.empty()) { //一层的顶点 int size q.size(); for(int i 0; i size; i) { UndirectedGraphNode *temp q.front(); UndirectedGraphNode *end m[temp]; q.pop(); for(int j 0; j temp-neighbors.size(); j) { if(s.find(temp-neighbors[j]) s.end()) { s.insert(temp-neighbors[j]); q.push(temp-neighbors[j]); } if(m.find(temp-neighbors[j]) m.end()) { UndirectedGraphNode* copiedNeighbor new UndirectedGraphNode(temp-neighbors[j]-label); m[temp-neighbors[j]] copiedNeighbor; } //将一个图接起来 end-neighbors.push_back(m[temp-neighbors[j]]); } } } return resultGraph; } };## [更多技术博客 http://vilins.top/](http://vilins.top/)
