[C++]LeetCode: 129 Clone Graph (图的深拷贝 BFS && DFS)

题目：

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

Nodes are labeled uniquely.

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
            / \
            \_/

   背景知识：

   1. 深拷贝和浅拷贝

   （1） 深拷贝是指源对象与拷贝对象互相独立，其中任何一个对象的改动都不会对另外一个对象造成影响。举个例子，一个人名叫张三，后来用他克隆（假设法律允许）了另外一个人，叫李四，不管是张三缺胳膊少腿还是李四缺胳膊少腿都不会影响另外一个人。比较典型的就是Value（值）对象，如预定义类型Int32，Double，以及结构（struct），枚举（Enum）等。

   考虑以下写法

   int source = int.MaxValue;//(1)初始化源对象为整数的最大值2,147,483,647

   int dest = source;//(2)赋值，内部执行深拷贝

   dest = 1024;//(3)对拷贝对象进行赋值

   source = 2048;//(4)对源对象进行赋值

   首先（2）中将source赋给dest，执行了深拷贝动作，其时dest和source的值是一样的，都是int.MaxValue；（3）对dest进行修改，dest值变为1024，由于是深拷贝，因此不会运行source，source仍然是int.MaxValue；（4）对source进行了修改，同样道理，dest仍然是1024，同时int.MaxValue的值也不变，仍然是2,147,483,647；只有source变成了2048。

   （2）浅拷贝是指源对象与拷贝对象共用一份实体，仅仅是引用的变量不同（名称不同）。对其中任何一个对象的改动都会影响另外一个对象。举个例子，一个人一开始叫张三，后来改名叫李四了，可是还是同一个人，不管是张三缺胳膊少腿还是李四缺胳膊少腿，都是这个人倒霉。比较典型的就有Reference（引用）对象，如Class（类）。

   考虑以下写法

   class Point

   {

   public int X;

   public int Y;

   public Point(int x, int y)

   {

   X = x;

   Y = y;

   }

   }

   Point source = new Point(10, 20);

   Point dest = source;

   dest.X = 20;

   由于Point现在是引用对象，因此Point dest=source的赋值动作实际上执行的是浅拷贝，最后的结果应该是source的X字段值也变成了20。即它们引用了同一个对象，仅仅是变量明source和dest不同而已。

   2. 数据结构和结构指针

   （1）数据结构：如果结构的定义包括参数model_name (可选)，该参数即成为一个与该结构等价的有效的类型名称。例如：

   struct products {
   char name [30];
   float price;
   };
   products apple;
   products orange, melon;
   

   我们首先定义了结构模块products，它包含两个域：name 和 price，每一个域是不同的数据类型。然后我们用这个结构类型的名称 (products) 来声明了 3个该类型的对象：apple, orange 和melon。

   在我们声明了确定结构模型的3个对象(apple, orange 和 melon)之后，我们就可以对它们的各个域(field)进行操作，这通过在对象名和域名之间插入符号点(.)来实现。例如，我们可以像使用一般的标准变量一样对下面的元素进行操作：

   apple.name
   apple.price
   orange.name
   orange.price
   melon.name
   melon.price （2）数据结构指针：

   就像其它数据类型一样，结构也可以有指针。其规则同其它基本数据类型一样：指针必须被声明为一个指向结构的指针：

   struct movies_t {
   char title [50];
   int year;
   };
   movies_t amovie;
   movies_t * pmovie;
   

   这里 amovie 是一个结构类型movies_t 的对象，而pmovie 是一个指向结构类型movies_t 的对象的指针。所以，同基本数据类型一样，以下表达式正确的：

   pmovie = &amovie;

   上面的代码中引入了一个重要的操作符：->。这是一个引用操作符，常与结构或类的指针一起使用，以便引用其中的成员元素，这样就避免使用很多括号。例如，我们用：

   pmovie->title

   来代替：

   (*pmovie).title

   以上两种表达式pmovie->title 和 (*pmovie).title 都是合法的，都表示取指针pmovie 所指向的结构其元素title 的值。我们要清楚将它和以下表达区分开：

   *pmovie.title

   它相当于

   *(pmovie.title)

   表示取结构pmovie 的元素title 作为指针所指向的值，这个表达式在本例中没有意义，因为title本身不是指针类型。

   下表中总结了指针和结构组成的各种可能的组合：

   表达式	描述	等价于
   pmovie.title	结构pmovie 的元素title
   pmovie->title	指针pmovie 所指向的结构其元素title 的值	(*pmovie).title
   *pmovie.title	结构pmovie 的元素title 作为指针所指向的值	*(pmovie.title)

   结构嵌套(Nesting structures)

   结构可以嵌套使用，即一个结构的元素本身又可以是另一个结构类型。例如：

   struct movies_t {
   char title [50];
   int year;
   }
   
   struct friends_t {
   char name [50];
   char email [50];
   movies_t favourite_movie;
   } charlie, maria;
   
   friends_t * pfriends = &charlie;
   

   因此，在有以上声明之后，我们可以使用下面的表达式：

   charlie.name
   maria.favourite_movie.title
   charlie.favourite_movie.year
   pfriends->favourite_movie.year
   

   (以上最后两个表达式等价)

   
   

   思路：题目的要求是让我们实现一个图的深拷贝。深拷贝指的是复制另外一个对象到自己的对象中，且两者不共享一个内存区，浅拷贝指的是两者共享一个内存区。所以我们需要new 来开辟新的内存区执行拷贝。还要注意一个问题。我们这个图实际上是个有向图，如果A有一个相邻顶点B，则A->B, 但是B能否到A取决于B是否有相邻顶点A. 也就是说如果B能达到A，说明图中存在环，如果不考虑环的存在，我们在拷贝中可能形成死循环。

   
   

   假设我们从图的A点出发，进行拷贝得到A(A2), 发现A有一个相邻顶点B，然后进行拷贝得到B(B2),然后链接A2->B2，使得B2成为A2的相邻顶点。接着，我们操作B, 发现B有一个相邻顶点A, 而A我们是已经进行过拷贝的了。如果我们又对A再次进行拷贝, 将形成个死循环，我们要做的仅是将B2->A2连接起来。如何才能避免这种再次拷贝呢？我们只需要一个map即可，每次我们做一份拷贝，就放入map中，下次查询，如果是已经有的copy就不再继续拷贝，只是连接。如果没有，就做拷贝，然后连接，然后放入map. map的key是原来的顶点，value是原来定点的copy版。

   具体解释可以看下这篇文章：clone graph part

   queue中维护的是未处理neighbor的顶点，也是未拷贝过的结点。

   map中的key,value分别保存copy过的原节点和copy节点。

   我们先copy根结点，然后放入队列，接下来进行广度优先搜索办法，不断处理队列中的节点，先得到当前节点和其copy版本，然后判断当前节点的所有neighbors, 如果已经拷贝过，只做连接操作，如果没有拷贝过，先进行拷贝，然后连接，然后放入map和queue.当队列中的元素都处理完，BFS结束，返回copy根结点。

   Attention:

   主要是基本方法的操作是否使用正确，加上一些细节的操作，需要仔细理解和记忆。属于基本操作的组合，容易混淆，应该仔细研究下代码。

   1. 注意基本操作的使用，比如结构体指针的内部元素的调用是用哪个操作符？"->"还是"." 还有分清楚操作的对象，然后决定用C++内的什么方法进行调用和操作。

   curClone->neighbors.push_back(neighborClone);     // 给curClone添加复制的neighbor

   
   2. 注意我们在拷贝过程中，总是要对原节点进行拷贝，处理连接关系时，也要在拷贝版本间进行连接。

    curClone->neighbors.push_back(neighborClone);     // 给curClone添加复制的neighbor

   
   3. map添加pair对，需要加“{}”。

   cmap.insert({neighbor, neighborClone});   //添加到map中

   
   

   复杂度：O(N),因为我们把每个结点都访问一遍，空间复杂度是栈或者队列加上map的大小，不会超过O(N)。

   AC Code: (BFS)

   /**
    * Definition for undirected graph.
    * struct UndirectedGraphNode {
    *     int label;
    *     vector neighbors;
    *     UndirectedGraphNode(int x) : label(x) {};
    * };
    */
   class Solution {
   public:
       UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
           if(node == NULL) return NULL;
           
           //开辟新的空间存储copy
           UndirectedGraphNode* copy = new UndirectedGraphNode(node->label);
           //查找去重用的map  unordered_map 放原始node和其复制品
           unordered_map cmap;
           //存储的队列，进行BFS
           queue graphQ;
           graphQ.push(node);               //根结点添加到队列
           cmap.insert({node, copy});   //把根节点和其复制品放入map  
           
           while(!graphQ.empty())
           {
               UndirectedGraphNode* cur = graphQ.front();   //当前处理对象
               graphQ.pop();
               UndirectedGraphNode* curClone = cmap[cur];   //当前处理对象的复制品 因为在前面的neighbor里已经被创建
               
               //对当前顶点的每一个neighbor进行判断，因为有的neighbor已经被复制，有的没有
               for(int i = 0; i < cur->neighbors.size(); i++)
               {
                   UndirectedGraphNode* neighbor = cur->neighbors[i];
                   //如果之前没有拷贝过
                   if(cmap.find(neighbor) == cmap.end())
                   {
                       UndirectedGraphNode* neighborClone = new UndirectedGraphNode(neighbor->label);
                       curClone->neighbors.push_back(neighborClone);   //给curClone添加复制的neighbor
                       cmap.insert({neighbor, neighborClone});   //添加到map中
                       graphQ.push(neighbor);   //添加到队列为了将来的遍历
                   }
                   else    // 之前已经被复制过的neighbor
                   {
                       UndirectedGraphNode* neighborClone = cmap[neighbor];   //从map中取出之前的copy版本
                       curClone->neighbors.push_back(neighborClone);     // 给curClone添加复制的neighbor
                   }
               }
           }
           
           return copy;
           
       }
   };

   
   

   AC Code: (DFS)

   将存储改成用stack存储结点，得到深度优先搜索。

   /**
    * Definition for undirected graph.
    * struct UndirectedGraphNode {
    *     int label;
    *     vector neighbors;
    *     UndirectedGraphNode(int x) : label(x) {};
    * };
    */
   class Solution {
   public:
       UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
           if(node == NULL) return NULL;
           stack stk;
           unordered_map cmap;
           UndirectedGraphNode* copy = new UndirectedGraphNode(node->label);
           stk.push(node);
           cmap.insert({node, copy});
           
           while(!stk.empty())
           {
               UndirectedGraphNode* cur = stk.top();
               stk.pop();
               UndirectedGraphNode* curClone = cmap[cur];   //浅拷贝，开始顶点的curClone和copy指向同一个地址 
               
               for(int i = 0; i < cur->neighbors.size(); i++)
               {
                   UndirectedGraphNode* neighbors = cur->neighbors[i];
                   if(cmap.find(neighbors) == cmap.end())
                   {
                       UndirectedGraphNode* neighborsClone = new UndirectedGraphNode(neighbors->label);
                       curClone->neighbors.push_back(neighborsClone);
                       cmap.insert({neighbors, neighborsClone});
                       stk.push(neighbors);
                   }
                   else
                   {
                       UndirectedGraphNode* neighborsClone = cmap[neighbors];
                       curClone->neighbors.push_back(neighborsClone);
                   }
               }
           }
           return copy;
       }
   };

   图的这两种遍历方法是很经典的问题，面试中虽然出现不多，但是还可能出现，出现了就必须要做好。所以要好好掌握，这道题主要考察基础的操作，最好是手写几遍。