leecode 解题总结：Clone GraphI

#include <iostream>#include <stdio.h>#include <vector>#include <string>#include <queue>#include <unordered_map>#include <sstream>using namespace std;/*问题:Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.OJ's undirected graph serialization:Nodes are labeled uniquely.We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.As an example, consider the serialized graph {0,1,2#1,2#2,2}.The graph has a total of three nodes, and therefore contains three parts as separated by #.First node is labeled as 0. Connect node 0 to both nodes 1 and 2.Second node is labeled as 1. Connect node 1 to node 2.Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.Visually, the graph looks like the following:       1      / /     /   /    0 --- 2         / /         /_/分析:题目是想拷贝一个无向图。具体要求是对每个结点需要求出其所有邻接点，并把所有邻接点存储到该结点自身的成员变量中。可能存在某些结点指向自身，这种情况，当前结点自身是否存储?需要的。参见序列化结果对于结点0：邻接点为1,2，即其成员变量只需要存储这两个结点对于结点结点1：给定了邻接点2，由于0又和2连接，因此虽然结点1存储的邻接点为2，但是却可以连接到0对于结点2：自循环，所以插入结点2现在给定一个有向图，肯定是比如给定初始结点0，找到邻接点为1,2，输出:0,1,2遍历不等于自身的邻居结点(防止陷入死循环)1：得到1的邻接点为2(也可能包含了0，只不过已经访问过，过滤),输出:1,2遍历邻接点2：输出:2，2现在猜这个图原始存的时候比如对于结点1，是否存储了0？应该是没有存储，题目的意思估计就是让我们存储一下。否则题目变成了结点的直接new和copy，这个就一个意思，考的是图的遍历。既然是拷贝，应该是一样的。其实考的知识点就是图的遍历，如果用广度优先，队列来做，设定一个访问标记，如果当前从队列中弹出的结点没有访问过，就遍历其所有的邻居结点，new出和其一样的；邻居结点和当前结点对每个未访问的邻居结点，压入到队列，最后直到队列为空，结束。这里的关键问题在于比如遍历结点0：结点0没有访问过，新建新的结点0，设置已经访问标记，可能需要设定两个队列，一个队列是原有队列，存储广度优先结果；另一个队列是存放已经建立的结点题目说：每个结点的标记是唯一的，直接用一个标记<int,Node*>来做输入：0 1 2#1 2#2 2输出:0 1 2#1 2#2 2关键：1采用广度优先搜索，建立label指向已经建立好结点的映射。队列中弹出的结点没有被访问过，设置访问标记    如果该结点的还没有在拷贝图中建立，就建立	获取结点的邻居结点，遍历每个邻居结点，如果拷贝图中对应邻居结点没有建立，也建立	如果邻居结点已经访问过，就过滤；否则，压入队列*/struct UndirectedGraphNode {   int label;   vector<UndirectedGraphNode *> neighbors;   UndirectedGraphNode(int x) : label(x) {};};class Solution {public:	UndirectedGraphNode* bfs(UndirectedGraphNode *node,unordered_map<int , UndirectedGraphNode*>& hasBuilt)	{		if(!node)		{			return NULL;		}		queue<UndirectedGraphNode *> nodes;		nodes.push(node);		UndirectedGraphNode* curNode;		unordered_map<UndirectedGraphNode* , bool> visited;		vector<UndirectedGraphNode *> neighbours;		UndirectedGraphNode* root = NULL;		UndirectedGraphNode* nextNode = NULL;		bool isFirst = true;		UndirectedGraphNode* newNode = NULL;		while(!nodes.empty())		{			curNode = nodes.front();			nodes.pop();			if(!curNode)			{				continue;			}			//如果当前结点已经访问过，直接跳过			if(visited.find(curNode) != visited.end())			{				continue;			}			visited[curNode] = true;//设置当前结点已经访问			//如果当前访问的结点没有建立			if(hasBuilt.find(curNode->label) == hasBuilt.end())			{				//这里有一个问题，结点1已经作为邻居结点被访问过了了，被建立过了，这里又要新建一遍				newNode = new UndirectedGraphNode(curNode->label);				hasBuilt[curNode->label] = newNode;			}			else			{				newNode = hasBuilt[curNode->label] ;			}			//保存首结点，用于返回			if(isFirst)			{				root = newNode;				isFirst = false;			}			vector<UndirectedGraphNode* > myNeighbours;			neighbours = curNode->neighbors;			if(neighbours.empty())			{				newNode->neighbors = myNeighbours;				continue;			}			int size = neighbours.size();			for(int i = 0 ; i < size ; i++)			{				nextNode = neighbours.at(i);				//如果邻居结点为空，直接跳过				if(!nextNode)				{					myNeighbours.push_back(NULL);					continue;				}				//判断邻居结点是否已经建立，如果没有建立，才建立。这里有个问题，结点2其实已经建立过了				if(hasBuilt.find(nextNode->label) == hasBuilt.end())				{					UndirectedGraphNode* tempNode = new UndirectedGraphNode(nextNode->label);					myNeighbours.push_back(tempNode);					hasBuilt[nextNode->label] = tempNode;				}				else				{					myNeighbours.push_back(hasBuilt[nextNode->label]);				}				//如果邻居结点已经访问过，就不压入队列				if(visited.find(nextNode) != visited.end())				{					continue;				}				nodes.push(nextNode);			}			//所有结点建立好之后，下面设定邻居结点集合			newNode->neighbors = myNeighbours;		}		return root;	}    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {		unordered_map<int , UndirectedGraphNode*> hasBuilt;        UndirectedGraphNode* root = bfs(node, hasBuilt);		_hasBuilt = hasBuilt;		_root = root;		return root;    }public:	UndirectedGraphNode* _root;	unordered_map<int , UndirectedGraphNode*> _hasBuilt;};vector<string> split(string& str , string& splitStr){	vector<string> result;	if(str.empty())	{		return result;	}	if(splitStr.empty())	{		result.push_back(str);		return result;	}	int beg = 0;	size_t pos = str.find(splitStr);	string partialStr;	while(string::npos != pos)	{		partialStr = str.substr(beg , pos - beg);		if(!partialStr.empty())		{			result.push_back(partialStr);		}		beg = pos + splitStr.length();		pos = str.find(splitStr , beg);	}	//防止 aa#aa，这种最后一次找不到	partialStr = str.substr(beg , pos - beg);	if(!partialStr.empty())	{		result.push_back(partialStr);	}	return result;}//按"# "号分割，然后按空格分割，0 1 2#1 2#2 2UndirectedGraphNode* buildGraph(string& str , unordered_map<int,UndirectedGraphNode* >& hasBuilt){	vector<string> result = split(str , string("#"));	if(result.empty())	{		return NULL;	}	vector<vector<string> > lines;	int size = result.size();	for(int i = 0 ; i < size ; i++)	{		vector<string> Words = split(result.at(i) , string(" "));		lines.push_back(words);	}	if(lines.empty())	{		return NULL;	}	//接下来找到所有的结点: 0 1 2 , 1 2 , 2 2	int lineSize = lines.size();	int wordSize;	UndirectedGraphNode* node = NULL ;	for(int i = 0 ; i < lineSize ; i++ )	{		wordSize=  lines.at(i).size();		UndirectedGraphNode* begNode = NULL;		vector<UndirectedGraphNode*> neighbours;		for(int j = 0 ; j < wordSize ; j++)		{			int value = atoi(lines.at(i).at(j).c_str());			//如果没有建立			if(hasBuilt.find(value) == hasBuilt.end())			{				node = new UndirectedGraphNode(value);				hasBuilt[value] = node;			}			else			{				node = hasBuilt[value];			}			//确定结点指向			if(j)			{				neighbours.push_back(node);			}			//根节点，需要建立指向			else			{				begNode = node;			}		}		begNode->neighbors = neighbours;	}	int value = atoi( lines.at(0).at(0).c_str());	return hasBuilt[value];}//如何递归删除图的所有结点，广度优先搜索(有环)，无需这样删除，之前不是保存了建立//结点的map吗。删除这个void deleteGraph(unordered_map<int , UndirectedGraphNode* > hasBuilt){	for(unordered_map<int , UndirectedGraphNode*>::iterator it = hasBuilt.begin() ; 		it != hasBuilt.end() ; it++)	{		delete it->second;		it->second = NULL;	}}//如何构建这个有向图string myBFS(UndirectedGraphNode* node){	queue<UndirectedGraphNode*> nodes;	nodes.push(node);	unordered_map<UndirectedGraphNode* , bool> visited;	vector<vector<int> >results;	vector<int> result;	while(!nodes.empty())	{		UndirectedGraphNode* curNode = nodes.front();		nodes.pop();		//如果当前结点已经访问过		if(visited.find(curNode) != visited.end())		{			continue;		}		visited[curNode] = true;		result.push_back(curNode->label);		//当前结点已经访问过，因此，需要		vector<UndirectedGraphNode*> neightbours = curNode->neighbors;		if(neightbours.empty())		{			continue;		}		int size = neightbours.size();		for(int i = 0 ; i < size ; i++)		{			UndirectedGraphNode* nextNode = neightbours.at(i);			if(!nextNode)			{				continue;			}			result.push_back(nextNode->label);			//子节点必须未被访问过			if(visited.find(nextNode) != visited.end())			{				continue;			}			nodes.push(nextNode);		}		results.push_back(result);		result.clear();	}	//转换结果	if(results.empty())	{		return "";	}	int size = results.size();	int len;	stringstream resultStream;	for(int i = 0 ; i < size ; i++)	{		stringstream stream;		len = results.at(i).size();		for(int j = 0 ; j < len ; j++)		{			stream << results.at(i).at(j) << " ";		}		stream << "#";		resultStream << stream.str();	}	return resultStream.str();}void PRint(vector<int>& result){	if(result.empty())	{		cout << "no result" << endl;		return;	}	int size = result.size();	for(int i = 0 ; i < size ; i++)	{		cout << result.at(i) << " " ;	}	cout << endl;}void process(){	 vector<int> nums;	 Solution solution;	 vector<int> result;	 char str[1024];	 while(gets(str))	 {		 string value(str);		 unordered_map<int , UndirectedGraphNode*> hasBuilt;		 UndirectedGraphNode* root = buildGraph(value, hasBuilt);		 UndirectedGraphNode* newRoot = solution.cloneGraph(root);		 string origin = myBFS(root);		 cout << origin << endl;		 string newResult = myBFS(newRoot);		 cout << newResult << endl;		 deleteGraph(hasBuilt);		 deleteGraph(solution._hasBuilt);	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}