无向连通图的深拷贝和打印

佚名 6年前 (2019-04-15) 随笔 1259人围观抢沙发百度已收录

题目：给定无向连通图中一个节点的引用，返回该图的深拷贝（克隆）。图中的每个节点都包含它的值和其邻居的列表。

要做深拷贝，必用map。但是对于这种图的生成，相当于要进行遍历，题目里也说了是连通图，所以给出一个结点就可以遍历整个图了，遍历的过程旨在生成没生成过的结点。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

遍历图自然会想到BFS，DFS。（hhhhh，写总结才发现原来不递归就是BFS...）

class Solution {
public:
    map<Node*,Node*> st;
    Node *cloneGraph_DFS(Node *node){
        
        auto p = st.find(node);
        if(p != st.end()){
            return st[node];
        }
        
        Node* ret = new Node(node->val,vector<Node*>());
        st[node] = ret;
        
        for(auto x:node->neighbors){
            ret->neighbors.push_back(cloneGraph_DFS(x));
        }
        
        return ret;                
    }
    Node *cloneGraph_BFS(Node *node){
        stack<Node*> nodes;
        
        nodes.push(node);
        
        while(!nodes.empty()){
            Node* a = nodes.top();nodes.pop();
            Node* ret;
            auto q = st.find(a);
            if(q == st.end()){
                ret = new Node(a->val,vector<Node*>());
                st[a]=ret;
            }
            else ret = st[a];
            
            for(auto x:a->neighbors){
                auto p = st.find(x);
                if( p == st.end()){
                    Node* x0 = new Node(x->val,vector<Node*>());
                    st[x] = x0;
                    ret->neighbors.push_back(x0);
                    nodes.push(x);
                }
                else ret->neighbors.push_back(p->second);
            }
        }
        
        return st[node];
    }
};

好啦，然后就是怎么打印这个图了，也是BFS和DFS的思路

set<Node*> node1;
void PrintNode_DFS(Node* node){
    auto p = node1.find(node);
    int a = node->val;
    if(p == node1.end()){
        node1.insert(node); 
        cout<<"id_"<<node->val<<"{";
        
        for(auto x:node->neighbors){
            int b = x->val;
            PrintNode_DFS(x);
        }
        
        cout<<"},";
        return;
    }
    else{
        cout<<"ref:"<<node->val<<",";
    }
}

set<Node*> node0;
void PrintNode_BFS(Node* res){
    stack<Node*> node;
    node.push(res);
    node0.insert(res);
    
    while(!node.empty()){
        Node* a = node.top();node.pop();
        cout<<a->val<<":";
        for(auto x:a->neighbors){
            auto p = node0.find(x);
            if(p == node0.end()){
                node0.insert(x);
                node.push(x);
            }
            cout<<x->val<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}