clone-graph优雅解释

本题要求复制一个无向图，图中每个节点都包含一个标签和它的邻居列表。
首先分析题意：
我上来就没读懂要干嘛，看各位好汉一顿BFS,DFS轰炸，彻底懵了。首先，复制无向图，不是简单地复制指针的指向，而是要创建全部节点，并按照原先的关系进行新图关系的组织。但是有个问题是：新节点的数量就那么多个，而neighbor中却有着错综的关系，如何保证每个节点独一份，而关系又能正确组织呢？那就是使用map了。另外，涉及到图的遍历问题，往往都是使用BFS和DFS进行求解。下面分别给出了这两种求解方法：
在这里，为了代码的清晰，将UndirectedGraphNode替换为GNode;
先来看BFS：

GNode* cloneGraph(GNode* node){
    if(!node) return nullptr;
    map<GNode*,GNode*> mp;    //创建map
    queue<GNode*> q;          //创建queue
    GNode* t = new GNode(node->label);  //新创建的节点
    mp[node] = t;           //建立映射，旧节点->新节点，方便通过旧节点查找
    q.push(node);             //将第一个节点入队
    while(!q.empty()){
        GNode* tmp = q.front();//将头节点作为label节点
        q.pop();
        for(GNode* neigh : tmp->neighbors){ //for循环找其neighbor节点
            if(mp.find(neigh) == mp.end()){  //尚未出现，就要创建
                GNode* neigh_new = new GNode(neigh->label);
                mp[neigh] = neigh_new;    //添加到映射，下次直接查询就行
                q.push(neigh);                //入队
            }
        mp[tmp]->neighbors.push_back(mp[neigh]);//新的push_back进来新的；
        }
    }
return t;
}

再来看看DFS，相对来说，它更简单一些，毕竟是递归嘛：

map<GNode*,GNode*> mp;
GNode* cloneGraph(GNode* node){
    if(!node)return nullptr;
    if(mp.find(node) == mp.end){
        GNode* tmp = new GNode(node->label);//对label节点
        mp[node] = tmp; //建立旧节点->新节点，方便下次直接查询（而不是创建）
        for(GNode* neigh: node->neighbors)  //对neighbors节点
            mp[node]->neighbors.push_back(cloneGraph(neigh));
    }
    return mp[node];
}

ffg