首页 > 代码库 > 【LeetCode】Clone Graph (2 solutions)
【LeetCode】Clone Graph (2 solutions)
Clone Graph
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 node0to both nodes1and2. - Second node is labeled as
1. Connect node1to node2. - Third node is labeled as
2. Connect node2to node2(itself), thus forming a self-cycle.
Visually, the graph looks like the following:
1 / / 0 --- 2 / \_/
这题只需一边遍历一遍复制就可以了。
因此至少可以用三种方法：
1、广度优先遍历(BFS)
2、深度优先遍历(DFS)
2.1、递归
2.2、非递归
解法一：广度优先遍历
变量说明：
hash表m用来保存原图结点与克隆结点的对应关系。
hash表f用来记录已经访问过的原图结点，防止循环访问。
队列q用于记录深度优先遍历的层次信息。
/** * Definition for undirected graph. * struct UndirectedGraphNode { * int label; * vector<UndirectedGraphNode *> neighbors; * UndirectedGraphNode(int x) : label(x) {}; * }; */class Solution {public: UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { if(node == NULL) return NULL; map<UndirectedGraphNode *, UndirectedGraphNode *> m; //record the <original node, clone node> pairs map<UndirectedGraphNode *, bool> f; //record original nodes that have been dealt with queue<UndirectedGraphNode *> q; //BFS, q store the original node UndirectedGraphNode *nodeClone = new UndirectedGraphNode(node->label); m[node] = nodeClone; //add <node, ret> to map q.push(node); f[node] = true; while(!q.empty()) { UndirectedGraphNode *temp = q.front(); //original node UndirectedGraphNode *tempClone = (m.find(temp))->second; //clone node q.pop(); for(vector<UndirectedGraphNode *>::size_type st = 0; st < temp->neighbors.size(); st ++) {//add neighbors of temp to the queue UndirectedGraphNode *neighbor = temp->neighbors[st]; map<UndirectedGraphNode *, bool>::iterator itf = f.find(neighbor); if(itf == f.end()) { f[neighbor] = true; q.push(neighbor); } map<UndirectedGraphNode *, UndirectedGraphNode *>::iterator it = m.find(neighbor); UndirectedGraphNode *neighborClone; if(it == m.end()) {//neighbors[st] not constructed yet neighborClone = new UndirectedGraphNode(neighbor->label); m[neighbor] = neighborClone; } else neighborClone = it->second; //connect neighbor to tempClone tempClone->neighbors.push_back(neighborClone); } } return nodeClone; }};
解法二：递归深度优先遍历(DFS)
/** * Definition for undirected graph. * struct UndirectedGraphNode { * int label; * vector<UndirectedGraphNode *> neighbors; * UndirectedGraphNode(int x) : label(x) {}; * }; */class Solution {public: map<UndirectedGraphNode *, UndirectedGraphNode *> f; UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { if(node == NULL) return NULL; map<UndirectedGraphNode *, UndirectedGraphNode *>::iterator it = f.find(node); if(it != f.end()) //if node is visited, just return the recorded nodeClone return f[node]; UndirectedGraphNode *nodeClone = new UndirectedGraphNode(node->label); f[node] = nodeClone; for(vector<UndirectedGraphNode *>::size_type st = 0; st < node->neighbors.size(); st ++) { UndirectedGraphNode *temp = cloneGraph(node->neighbors[st]); if(temp != NULL) nodeClone->neighbors.push_back(temp); } return nodeClone; }};
【LeetCode】Clone Graph (2 solutions)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。