程序员人生 网站导航

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 #.

  1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
  2. Second node is labeled as 1. Connect node 1 to node 2.
  3. 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]; } };


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

最新技术推荐