图克隆（C++实现）

// Type your C++ code and click the "Run Code" button!
// Your code output will be shown on the left.
// Click on the "Show input" button to enter input data to be read (from stdin).

#include <iostream>
using namespace std;

typedef struct GNode {
    int val;
    vector<GNode *> nbs;
} Node;

typedef unordered_map<Node *, Node *> CloneMap;
typedef unordered_map<Node *, bool> VisitedMap;

// clone graph
Node * clone_graph(Node * graph) {
    if(!graph) return NULL;
    
    CloneMap map;
    queue<Node *> q;
    q.push(graph);
    
    Node *nc = new Node;
    nc->val = graph->val;
    map[graph] = nc;
    
    while(!q.empty()) {
        Node *&front = q.front(); 
        Node *fc = map[front];
        vector<Node *> nbs = front->nbs;
        vector<Node *>::const_iterator it = nbs.begin();
        
        while(it != nbs.end()) {
            Node *ic;
            if(!map[*it]) {
                ic = new Node;
                ic->val = (*it)->val;
                map[*it] = ic;
                q.push(*it);
            } else {
                ic = map[*it];
            }
            fc->nbs.push_back(ic);
            it ++;
        }        
        q.pop();
    }
    return nc;
}


// print graph
void print_graph(Node *graph) {
    if(!graph) return;
    
    VisitedMap map;
    queue<Node *> q;
    q.push(graph);
    
    while(!q.empty()) {
        Node *&front = q.front();
        
        if(!map[front]){
            cout<<front->val<<" ";
            map[front] = true;
        }
        
        vector<Node *> nbs = front->nbs;
        vector<Node *>::const_iterator cit = nbs.begin();
        while(cit != nbs.end()) {
            if(!map[*cit]) {
                cout<<(*cit)->val<<" ";
                map[*cit] = true;
                q.push(*cit);
            }
            cit ++;
        }
        q.pop();
    }
    cout<<endl;
}

int main() {
    Node *n1 = new Node;
    n1->val = 1;
    Node *n2 = new Node;
    n2->val = 2;
    Node *n3 = new Node;
    n3->val = 3;
    Node *n4 = new Node;
    n4->val = 4;
    Node *n5 = new Node;
    n5->val = 5;
    
    n1->nbs.push_back(n2);
    n2->nbs.push_back(n1);
    n1->nbs.push_back(n3);
    n3->nbs.push_back(n1);
    n2->nbs.push_back(n3);
    n3->nbs.push_back(n2);
    n3->nbs.push_back(n4);
    n4->nbs.push_back(n3);
    n4->nbs.push_back(n5);
    n5->nbs.push_back(n4);
    
    // test clone function
    Node *nc = clone_graph(n2);
    
    print_graph(n1);
    print_graph(n2);
    print_graph(nc);
    
    return 0;
}

欢迎关注微信公众号——计算机视觉：