leetcode || 133、Clone Graph

栏目：框架设计时间：2015-05-21 08:10:33

problem：

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 / \_/

Hide Tags

Depth-first Search Breadth-first Search Graph

题意：复制图（结构和数据不变，要新建节点）

thinking：

（1）要新建图的各个节点，保持邻接关系不变。

（2）采取unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> 存储原节点和新节点。而不是unordered_map<int, UndirectedGraphNode*>，
效力要高很多

（3）采取BFS思想，将原节点的邻接节点全部入栈或堆栈，遍历节点。

（4）map中查找key是不是存在可以调用find（),也能够调用count（），后者效力更高

（5）提交没通过，结果不正确：

Input:{0,1,5#1,2,5#2,3#3,4,4#4,5,5#5}

Output:{0,5,1#1,5,2#2,3#3,4,4#4,5,5#5}

Expected:{0,1,5#1,2,5#2,3#3,4,4#4,5,5#5}

其实，结果是正确的，由于对无向图，节点出现的顺序不影响图的结构，只能说这个验证程序只验证了1种结果

code：

class Solution { public: UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> record; if(node == NULL) return node; stack<UndirectedGraphNode*> queue; queue.push(node); while(!queue.empty()) { UndirectedGraphNode *nextNode = queue.top(); queue.pop(); if(!record.count(nextNode)) { UndirectedGraphNode *newNode = new UndirectedGraphNode(nextNode->label); record[nextNode] = newNode; } for(int i = nextNode->neighbors.size()⑴; i >= 0 ; i --) { UndirectedGraphNode *childNode = nextNode->neighbors[i]; if(!record.count(childNode)) { UndirectedGraphNode *newNode = new UndirectedGraphNode(childNode->label); record[childNode] = newNode; queue.push(childNode); } record[nextNode]->neighbors.push_back(record[childNode]); } } return record[node]; } };

------分隔线----------------------------