clone-graph

题目描述

给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。

题解

1. 使用 HashMap 存储所有访问过的节点和克隆节点。HashMap 的 key 存储原始图的节点，value 存储克隆图中的对应节点。visited 用于防止陷入死循环，和获得克隆图的节点。

2. 将第一个节点添加到队列。克隆第一个节点添加到名为 visited 的 HashMap 中。

3. BFS 遍历

   从队列首部取出一个节点。
   遍历该节点的所有邻接点。
   如果某个邻接点已被访问，则该邻接点一定在 visited 中，那么从 visited 获得该邻接点。
   否则，创建一个新的节点存储在 visited 中。
   将克隆的邻接点添加到克隆图对应节点(步骤1中得到的首部节点)的邻接表中。

作者：LeetCode
链接：https://leetcode-cn.com/problems/clone-graph/solution/ke-long-tu-by-leetcode/

#include<unordered_map>
Node* cloneGraph(Node* node) {
	if (!node)return NULL;
	unordered_map<Node*, Node*>visited;
	visited[node] = new Node(node->val);
	queue<Node*>que;
	que.push(node);

	Node* tmpNode;
	vector<Node*> tmpVec;
	while (!que.empty())
	{
		tmpNode=que.front();
		que.pop();
		tmpVec = tmpNode->neighbors;
		for (Node* n : tmpVec)
		{
			if (!visited.count(n))
			{
				Node* newNode = new Node(n->val);
				visited[n] = newNode;
				que.push(n);
			}
			visited[tmpNode]->neighbors.push_back(visited[n]);
		}
	}
	return visited[node];
}