DFS&BFS
队列queue
unordered_map容器（无序map容器）
C++中for auto的用法
//克隆图
#include<iostream>
#include<string>
#include<unordered_map>
#include<vector>
#include<queue>
using namespace std;
//图节点定义
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;
}
};
unordered_map<int, Node*> map;
//方法一：深度优先搜索
Node* cloneGraph(Node* node) {
//空节点不克隆
if (!node) {
return nullptr;
}
//克隆的节点不克隆
if (map.find(node->val) != map.end()) {
return map[node->val];
}
//创建克隆节点
Node* clonenode = new Node(node->val);
map[node->val] = clonenode; //存储克隆节点
//克隆邻接表
for (auto& n : node->neighbors) {
clonenode->neighbors.push_back(cloneGraph(n));
}
return clonenode;
}
//方法二：广度优先搜索
Node* cloneGraph(Node* node) {
//空节点不拷贝
if (!node) {
return nullptr;
}
map[node->val] = new Node(node->val); //存储克隆节点
queue<Node*> _queue;
_queue.push(node); //当前节点入队
Node* temp; //当前处理的节点
while (!_queue.empty()) {
temp = _queue.front(); //取队首元素
_queue.pop(); //弹出队首元素
Node* cloneNode = map[temp->val]; //取当前节点克隆节点
for (auto& neighbor : temp->neighbors) {
if (map.find(neighbor->val) == map.end()) { //邻居未拷贝
map[neighbor->val] = new Node(neighbor->val); //存储克隆节点
_queue.push(neighbor); //邻居入队
}
cloneNode->neighbors.push_back(map[neighbor->val]); //存储邻接关系
}
}
return map[node->val];
}
int main()
{
return 0;
}