Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
/**
* Definition for undirected graph.
* struct UndirectedGraphNode {
* int label;
* vector<UndirectedGraphNode *> neighbors;
* UndirectedGraphNode(int x) : label(x) {};
* };
*/
图的遍历有两种方法，一种是广度优先搜索，一种是深度优先搜索。
最naive的方法就是遍历一边，然后得到结果。
但是有一个需要考虑的点是，如果出现了重复怎么办
B
/ \
/ \
A------------D
解决办法是，可以建一个 map 来存储已经遍历过的节点， map的pair的内容是 <oldnode, new node>
然后思路是，
1. BSF 遍历图
2. 如果节点的邻接节点没有在已经遍历过的map中出现，那么新建一个节点，更新map。
如果这个节点已经在遍历的map中出现过，那么就需要更新邻接关系即可。
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { // BSF if(node == NULL) return NULL; queue<UndirectedGraphNode*> mq; unordered_map<UndirectedGraphNode *, UndirectedGraphNode *> mp; UndirectedGraphNode * newnode; mq.push(node); newnode = new UndirectedGraphNode(node->label); mp[node] = newnode; while(!mq.empty()) { UndirectedGraphNode * tmp = mq.front(); mq.pop(); for(int i=0; i<tmp->neighbors.size(); i++) { UndirectedGraphNode* neighbor = tmp->neighbors[i]; if(mp.find(neighbor)== mp.end()) { newnode = new UndirectedGraphNode(neighbor->label); //新建一个节点 mp[neighbor]= newnode; //把这个节点加到map中去 mp[tmp]->neighbors.push_back(newnode); //更新拷贝后的节点的邻接关系。 mq.push(neighbor); // DSF 的入queue } else { mp[tmp]->neighbors.push_back(mp[neighbor]); //因为已经遍历过了，那就只需要更新邻接关系即可 } } } return mp[node]; }
这个题目的思路还可以用在这道题目上
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
public: RandomListNode *copyRandomList(RandomListNode *head) { RandomListNode * result; unordered_map<RandomListNode*, RandomListNode*> mp; RandomListNode* node = head; if(head == NULL) return head; while(node!= NULL) { RandomListNode* tmpnode = new RandomListNode(node->label); mp[node] = tmpnode; // node= node->next;// go to next node } node = head; while(node!=NULL) { RandomListNode *randnode = node->random; RandomListNode *next = node->next; mp[node]->random = mp[randnode]; mp[node]->next = mp[next]; node= node->next; } return mp[head]; }
对于所有有不确定的重复的情况，都可以使用类似的map来解决。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。