复制一个无向图，图中每一个结点，包含了一个label，以及其neighbors的一个链表。 节点的标签是唯一的。我们使用#作为每个节点的分隔符，并且使用逗号作为节点标签与节点的每一个临近节点的分隔符。例如：{0,1,2#1,2#2,2} 该图一共有3个节点，分为#分隔开的三个部分。 1.第1个节点的标签是0，节点0与节点1和节点2相连。 2.第2个节点的标签是1，节点1和节点2相连。 3.第1个节点的标签是2，节点2其自身相连。
借助额外的数据结构map来存储源节点和拷贝节点之间的对应关系。有了这个关系，在遍历图的过程中，就可以同时处理访问节点以及访问节点的拷贝节点，一次完成。 本题也可以通过多次遍历来插入拷贝节点，链接拷贝节点以及将拷贝结点拆分出来，缺点是需要对图多次遍历。
/** * 无向图(undirected graph)的定义 * struct UndirectedGraphNode { * int label; * vector<UndirectedGraphNode *> neighbors;//相邻的结点,可以有n个 * UndirectedGraphNode(int x) : label(x) {}; //构造？ * }; */ UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node){ if (node == NULL) return NULL; unordered_map<UndirectedGraphNode *, UndirectedGraphNode *> nodeMap; queue<UndirectedGraphNode *> visit; visit.push(node); UndirectedGraphNode *nodeCopy = new UndirectedGraphNode(node->label); nodeMap[node] = nodeCopy; while(visit.size() > 0){ UndirectedGraphNode *cur = visit.front(); visit.pop(); for(int i=0; i < cur->neighbors.size(); ++i){ UndirectedGraphNode *neighb = cur->neighbors[i]； if(nodeMap.find(neighb) == nodeMap.end() ){ //还未复制该相邻结点，创建一个并连接这个副本 UndirectedGraphNode* neighbCopy = new UndirectedGraphNode(neighb->label); nodeMap[cur]->neighbors.push_back(neighbCopy); nodeMap[neighb] = neighbCopy; visit.push(neighb); } else{ //已经复制过该相邻结点，连接它 nodeMap[cur]->neighbors.push_back(nodeMap[neighb]); } } } return nodeCopy; }