Leetcode: Clone Graph

一时失言乱红尘 2022-08-04 14:52 113阅读 0赞

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<UndirectedGraphNode*> neighbors; * UndirectedGraphNode(int x) : label(x) {}; * }; */
    class Solution 
    {
    public:
        UndirectedGraphNode* cloneGraph(UndirectedGraphNode* node) 
        {
            if (node == nullptr)    return nullptr;
    
            // map的key为原始节点，value为拷贝的节点
            unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> copyMap;
            // 完成给定节点的图的拷贝工作
            clone(node, copyMap);
    
            return copyMap[node];
        }
    private:
        static UndirectedGraphNode* clone(UndirectedGraphNode* node, unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> &copyMap)
        {
            // 如果该节点已经拷贝过，直接返回该节点的拷贝
            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 copiedNode;
        }
    };