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 #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. 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重用。

   另外需要一個map， 映射，當前節點，和其對應的復制節點。

   訪問每一個節點時，需要復制其鄰接邊。對題目來講，就是復制其 neighbours數組。

   當邊所引用的節點不存在時，需要創建此結點。

    

   以下深度優先實現方式。在leetcode上實際執行時間為 72ms。

    

   /**
    * Definition for undirected graph.
    * struct UndirectedGraphNode {
    *     int label;
    *     vector neighbors;
    *     UndirectedGraphNode(int x) : label(x) {};
    * };
    */
   class Solution {
   public:
       UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
           if (!node) return node;
           stack s;
           unordered_map m;
           s.push(node);
           auto root = new UndirectedGraphNode(node->label);
           m[node] = root;
           while (!s.empty()) {
               node = s.top();
               s.pop();
               auto node_copy = m[node];
               for (auto neighbor: node->neighbors) {
                   auto © = m[neighbor];
                   if (!copy) {
                       s.push(neighbor);
                       copy = new UndirectedGraphNode(neighbor->label);
                   }
                   node_copy->neighbors.push_back(copy);
               }
           }
           return root;
       }
   };

   
   廣度優先實際方式。在leetcode上執行時間為76ms。

    

   即將上面算法的stack換成了queue。

    

   class Solution {
   public:
       UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
           if (!node) return node;
           queue q;
           unordered_map m;
           q.push(node);
           auto root_copy = new UndirectedGraphNode(node->label);
           m[node] = root_copy;
           while (!q.empty()) {
               node = q.front();
               q.pop();
               auto node_copy = m[node];
               for (auto neighbor: node->neighbors) {
                   auto © = m[neighbor];
                   if (!copy) {
                       q.push(neighbor);
                       copy = new UndirectedGraphNode(neighbor->label);
                   }
                   node_copy->neighbors.push_back(copy);
               }
           }
           return root_copy;
       }
   };