BFS：克隆图

亦凉 2023-10-06 10:07 2阅读 0赞

## BFS：克隆图 ##

#### 问题： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 3]

#### 思路： ####

首先建立与原图节点个数相等的新节点，然后按照原图中边的连接规则，对新图中对应节点进行连接

在建立新节点的过程中用map保存新节点与原节点的映射关系

首先使用BFS遍历所有节点，每遍历到一个节点，创建一个与之对应的新节点，并用map保存它们的映射关系

遍历map中所有的原图节点，找到它的邻接点数组，遍历该数组，按照原连接规则将新图的对应节点相连

#### 代码： ####

/*
    // Definition for a Node.
    class Node {
    public:
        int val;
        vector<Node*> neighbors;
        
        Node() {
            val = 0;
            neighbors = vector<Node*>();
        }
        
        Node(int _val) {
            val = _val;
            neighbors = vector<Node*>();
        }
        
        Node(int _val, vector<Node*> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }
    };
    */
    
    class Solution {
        
    public:
        Node* cloneGraph(Node* node) {
        
            if( node==NULL )
                return node;
            unordered_map< Node*,Node* > table;
            queue<Node*> q;
            q.push( node );
            while( q.size()!=0 )
            {
        
                Node* temp=q.front();
                q.pop();
                Node* p=new Node( temp->val,{
        } );
                table[ temp ]=p;
                for( Node* adj : temp->neighbors )
                {
        
                    if( table.find( adj )==table.end() )
                        q.push( adj );
                }
            }
            auto i=table.begin();
            for( ;i!=table.end();i++ )
            {
        
                for( auto temp:i->first->neighbors )
                {
        
                    i->second->neighbors.push_back( table.find( temp )->second );
                }
            }
            return table.find(node)->second;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200531204623949.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200531204645703.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200531204703708.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200531204719185.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70