[LeetCode]Clone Graph

用BFS或者DFS在遍历原图的时候建新的节点，唯一的问题是，如果图存在环，那么我们clone的新图需要reference一个以前已经建好的节点（没有环的时候不需要）。所以我们需要一个map来记录原节点和新节点的对应关系，如果map包含节点直接return，如果不存在，新建节点继续遍历。
BFS的做法如下:

	/**
	* Definition for undirected graph.
	* struct UndirectedGraphNode {
	* int label;
	* vector<UndirectedGraphNode *> neighbors;
	* UndirectedGraphNode(int x) : label(x) {};
	* };
	*/
	class Solution {
	public:
	UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
	if(!node)return nullptr;
	unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> map;
	queue<UndirectedGraphNode*> q;
	q.push(node);
	UndirectedGraphNode* root = new UndirectedGraphNode(node->label);
	map[node] = root;
	while(q.size())
	{
	auto curr = q.front();
	auto copy = map[curr];
	q.pop();
	for(auto next : curr->neighbors)
	{
	if(map.find(next) == map.end())
	{
	UndirectedGraphNode* nextCopy = new UndirectedGraphNode(next->label);
	map[next] = nextCopy;
	q.push(next);
	}
	copy->neighbors.emplace_back(map[next]);
	}
	}
	return root;
	}
	};

view raw Clone Graph.cpp hosted with ❤ by GitHub

DFS的做法如下，我们用的是Postorder遍历:

	/**
	* Definition for undirected graph.
	* struct UndirectedGraphNode {
	* int label;
	* vector<UndirectedGraphNode *> neighbors;
	* UndirectedGraphNode(int x) : label(x) {};
	* };
	*/
	class Solution {
	public:
	UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
	if(!node)return nullptr;
	unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> map;
	return dfs(node, map);
	}
	private:
	UndirectedGraphNode* dfs(UndirectedGraphNode* node, unordered_map<UndirectedGraphNode*, UndirectedGraphNode*>& map)
	{
	if(map.find(node) != map.end())
	return map[node];
	UndirectedGraphNode* nodeCopy = new UndirectedGraphNode(node->label);
	map[node] = nodeCopy;
	for(auto next : node->neighbors)
	nodeCopy->neighbors.emplace_back(dfs(next, map));
	return nodeCopy;
	}
	};

view raw Clone Graph2.cpp hosted with ❤ by GitHub