BFS：克隆图
问题：
思路：
首先建立与原图节点个数相等的新节点，然后按照原图中边的连接规则，对新图中对应节点进行连接
在建立新节点的过程中用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;
}
};
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/153833.html
