首页 > 程序开发 > 软件开发 > C++ >

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

2015-01-29

题目: Clone an undirected graph Each node in the graph contains a label and a list of its neighbors OJ & 039;s undirected graph serialization: Nodes are labeled uniquely W

题目:

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

    背景知识:

    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有一个湘…"http://www.2cto.com/database/DB2/" target="_blank" class="keylink">DB2ralteNCo6zIu7rzvfjQ0L+9sbS1w7W9QihCMiksyLu688G0vdNBMi0+QjKjrMq5tcNCMrPJzqpBMrXEz+DB2ralteOho73T18WjrM7Sw8ey2df3Qiwgt6LP1kLT0NK7uPbP4MHatqW140EsILb4Qc7Sw8fKx9LRvq29+NDQuf2/vbG0tcTBy6GjyOe5+87Sw8fT1rbUQdTZtM69+NDQv72xtCwgvavQzrPJuPbLwNGtu7ejrM7Sw8fSqtf2tcS99srHvatCMi0+QTLBrL3TxvDAtKGjyOe6zrLFxNyx3MPi1eLW1tTZtM6/vbG0xNijv87Sw8fWu9Do0qrSu7j2bWFwvLS/yaOsw7+0zs7Sw8fX9tK7t92/vbG0o6y+zbfFyOttYXDW0KOsz8K0zrLp0a+jrMjnufvKx9LRvq3T0LXEY29web7NsrvU2bzM0Pi/vbG0o6zWu8rHway906GjyOe5+8O709CjrL7N1/a/vbG0o6zIu7rzway906OsyLu687fFyOttYXAuCiBtYXC1xGtlecrH1K3AtLXEtqW146OsdmFsdWXKx9StwLS2qLXjtcRjb3B5sOahozwvcD4KPHA+vt/M5b3iys2/ydLUv7TPwtXixqrOxNXCo7pjbG9uZSBncmFwaCBwYXJ0PC9wPgo8cD5xdWV1ZdbQzqy7pLXEysfOtLSmwO1uZWlnaGJvcrXEtqW146Os0rLKx860v72xtLn9tcS94bXjoaM8L3A+CjxwPm1hcNbQtcRrZXksdmFsdWW31rHwsaO05mNvcHm5/bXE1K292rXjus1jb3B5vdq146GjPC9wPgo8cD7O0sPHz8hjb3B5uPm94bXjo6zIu7rzt8XI67bTwdCjrL3Tz8LAtL340NC547bI08XPyMvRy/ew7Leoo6yyu7bPtKbA7bbTwdDW0LXEvdq146Osz8i1w7W9tbHHsL3ateO6zcbkY29webDmsb6jrMi7uvPF0LbPtbHHsL3ateO1xMv509BuZWlnaGJvcnMsIMjnufvS0b6tv72xtLn9o6zWu9f2way907LZ1/ejrMjnufvDu9PQv72xtLn9o6zPyL340NC/vbG0o6zIu7rzway906OsyLu687fFyOttYXC6zXF1ZXVlLrWxttPB0NbQtcTUqsvYtry0psDtzeqjrEJGU73hyvijrLe1u9hjb3B5uPm94bXjoaM8L3A+CjxwPjxzdHJvbmc+QXR0ZW50aW9uOjwvc3Ryb25nPjwvcD4KPHA+PHN0cm9uZz7W99Kqyse7+bG+t723qLXEstnX98rHt/HKudPD1f3It6OsvNPJz9K70KnPuL3atcSy2df3o6zQ6NKq19DPuMDtveK6zbzH0uSho8r009q7+bG+stnX97XE1+m6z6OsyN3S17vsz/2jrNOmuMPX0M+40dC+v8/CtPrC66GjPC9zdHJvbmc+PC9wPgo8cD48c3Ryb25nPjEuINei0uK7+bG+stnX97XEyrnTw6OsscjI573hubnM5da41eu1xMTasr/UqsvYtcS199PDysfTw8TEuPay2df3t/ujvw=="->"还是"." 还有分清楚操作的对象,然后决定用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;
        }
    };
    图的这两种遍历方法是很经典的问题,面试中虽然出现不多,但是还可能出现,出现了就必须要做好。所以要好好掌握,这道题主要考察基础的操作,最好是手写几遍。

相关文章
最新文章
热点推荐