这些小活动你都参加了吗?快来围观一下吧!>>
电子产品世界 » 论坛首页 » 嵌入式开发 » STM32 » clone-graph

共2条 1/1 1 跳转至

clone-graph

高工
2018-01-30 12:08:29     打赏

Clone an undirected graph. Each node in the graph contains alabeland a list of itsneighbors.


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 as0. Connect node0to both nodes1and2.

  2. Second node is labeled as1. Connect node1to node2.

  3. Third node is labeled as2. Connect node2to node2(itself), thus forming a self-cycle.



Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/



题意:

克隆一个无向图,途中的每个节点包含一个标签及其邻居的列表

Oj对于无向图的序列化;

节点的标签是唯一的。

我们使用#作为节点的分割符,使用逗号,作为节点标签以及每个邻居之间的分割符;


例如,考虑序列化图0,1,2#1,2#2,2


上图包含三个几点,

第一个节点标签为0, 节点0与节点1、2相连;

第二个节点标签为1,节点1与节点2相连;

第三个节点为2,节点2与节点2相连,形成了一个环;


这道题主要是数据结构的应用吧,用一个队列存放途中还未被访问的节点,
用一个map存放克隆的新节点。对于队列中的节点,访问其邻居节点,如果该
邻居已经被克隆,那么只需要维护克隆节点之间的邻居关系即可,如果该邻居
尚未被克隆,那么需要new一个新节点作为它的克隆,并维护克隆后的邻居关系;



[cpp] view plain copy
  1. class Solution {  

  2. public:  

  3.     

  4.     map<int,UndirectedGraphNode*> record;  

  5.     UndirectedGraphNode *clone(UndirectedGraphNode *node) {  

  6.         UndirectedGraphNode *ngraph,*p;  

  7.         map<int,UndirectedGraphNode*>::iterator iter;  

  8.         p=node;  

  9.         iter=record.find(p->label);  

  10.         if(iter!=record.end())  

  11.             return iter->second;  

  12.         ngraph=new UndirectedGraphNode(p->label);  

  13.         record.insert(map<int,UndirectedGraphNode*>::value_type(p->label,ngraph));  

  14.         for(int i=0;i<p->neighbors.size();i++){  

  15.             ngraph->neighbors.push_back(clone(p->neighbors[i]));  

  16.         }  

  17.         return ngraph;  

  18.     }  

  19.     UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node){  

  20.         UndirectedGraphNode *ngraph;  

  21.         if(node==NULL)  

  22.             return NULL;  

  23.         record.clear();  

  24.         ngraph=clone(node);  

  25.         return ngraph;  

  26.     }  

  27. };




院士
2018-01-31 10:44:10     打赏
2楼

听上去就非常非常的高深了


共2条 1/1 1 跳转至

回复

匿名不能发帖!请先 [ 登陆 注册 ]