lintcode137. 克隆图

偏执的太偏执、 2023-07-05 10:07 19阅读 0赞

克隆一张无向图. 无向图的每个节点包含一个 label 和一个列表 neighbors. 保证每个节点的 label 互不相同.

你的程序需要返回一个经过深度拷贝的新图. 新图和原图具有同样的结构, 并且对新图的任何改动不会对原图造成任何影响.

样例
    样例1
    
    输入:
    {
        1,2,4#2,1,4#4,1,2}
    输出: 
    {
        1,2,4#2,1,4#4,1,2}
    解释:
    1------2  
     \     |  
      \    |  
       \   |  
        \  |  
          4   
    说明
    关于无向图的表示: http://www.lintcode.com/help/graph/
    
    注意事项
    你需要返回与给定节点具有相同 label 的那个节点.

建立新图中label和UndirectedGraphNode \*\*的map映射，看了网上的后，很多都是建立新旧图两者的UndirectedGraphNode \*相互映射

/**
     * Definition for undirected graph.
     * struct UndirectedGraphNode {
     *     int label;
     *     vector<UndirectedGraphNode *> neighbors;
     *     UndirectedGraphNode(int x) : label(x) {};
     * };
     */
    
    class Solution {
        
    public:
        /**
         * @param node: A undirected graph node
         * @return: A undirected graph node
         */
        UndirectedGraphNode* cloneGraph(UndirectedGraphNode* node) {
        
            // write your code here
            if(node==NULL) return NULL;
            UndirectedGraphNode*newnode=new UndirectedGraphNode(node->label);
            queue<UndirectedGraphNode*> oldq;
            set<UndirectedGraphNode*>judge;
            map<int,UndirectedGraphNode*> m;//记录新图的结点值和对应的点，防止重复建立对象
            m[newnode->label]=newnode;
            oldq.push(node);
            while(!oldq.empty())//bfs
            {
        
                UndirectedGraphNode*oldn=oldq.front();
                UndirectedGraphNode*newn=m[oldn->label];
                oldq.pop();
                if(judge.count(oldn))//判断该点是否已经搜索过
                    continue;
                else
                    judge.insert(oldn);
                for (int i = 0; i < oldn->neighbors.size(); i++) {
        
                    /* code */
                    UndirectedGraphNode*tmp;
                    if(m.find(oldn->neighbors[i]->label)!=m.end())tmp=m[oldn->neighbors[i]->label];
                    else tmp=new UndirectedGraphNode(oldn->neighbors[i]->label);
                    newn->neighbors.push_back(tmp);
                    oldq.push(oldn->neighbors[i]);
                    m[oldn->neighbors[i]->label]=tmp;
                }
            }
            return newnode;
        }
    };

/**
     * Definition for undirected graph.
     * struct UndirectedGraphNode {
     *     int label;
     *     vector<UndirectedGraphNode *> neighbors;
     *     UndirectedGraphNode(int x) : label(x) {};
     * };
     */
    class Solution {
        
    public:
        /**
         * @param node: A undirected graph node
         * @return: A undirected graph node
         */
        UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        
            // write your code here
            if(node == NULL) {
        
                return node;
            }
    
            queue<UndirectedGraphNode*> willVisit;
            map<UndirectedGraphNode*, bool> isVisited;
            map<UndirectedGraphNode*, UndirectedGraphNode*> oldToNew;
    
            UndirectedGraphNode * newNode = new UndirectedGraphNode(node->label);
            isVisited[node] = true;
            oldToNew[node] = newNode;
            willVisit.push(node);
    
            while(!willVisit.empty()) {
        
                node = willVisit.front();
                willVisit.pop();
                for(int i=0; i<node->neighbors.size(); i++) {
        
                    if(isVisited[node->neighbors[i]] == false) {
        
                        UndirectedGraphNode * temp = new UndirectedGraphNode(node->neighbors[i]->label);
                        isVisited[node->neighbors[i]] = true;
                        oldToNew[node->neighbors[i]] = temp;
                        oldToNew[node]->neighbors.push_back(temp);
                        willVisit.push(node->neighbors[i]);
                    }
                    else {
        
                        oldToNew[node]->neighbors.push_back(oldToNew[node->neighbors[i]]);
                    }
                }
            }
            return newNode;
        }
    原文链接：https://www.cnblogs.com/libaoquan/p/7222910.html
    };