首页 > 代码库 > 【leetcode】Clone Graph
【leetcode】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 node0
to both nodes1
and2
. - Second node is labeled as
1
. Connect node1
to node2
. - Third node is labeled as
2
. Connect node2
to node2
(itself), thus forming a self-cycle.
Visually, the graph looks like the following:
1 / / 0 --- 2 / \_/
题解:利用DFS递归的方法克隆图,用hashmap保存原图中的节点和新图中的节点的对应关系。而且利用这个hashmap可以在O(1)的时间内判断一个节点是否被克隆过,并且知道克隆它得到的新节点。
实现一个克隆节点的方法,在这个方法中:
- 判断这个节点是否被clone过了,如果是,返回它对应的clone节点;
- 如果没有被clone过,那么新建节点为该节点的clone节点,并且递归的clone它的邻居节点,放入该节点的neighbors列表里面;
代码如下:
1 /** 2 * Definition for undirected graph. 3 * class UndirectedGraphNode { 4 * int label; 5 * List<UndirectedGraphNode> neighbors; 6 * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); } 7 * }; 8 */ 9 public class Solution {10 private HashMap<UndirectedGraphNode,UndirectedGraphNode> mapClone = new HashMap<UndirectedGraphNode,UndirectedGraphNode>();11 12 private UndirectedGraphNode cloneNode(UndirectedGraphNode node){13 if(node == null)14 return null;15 //if this node already has a clone16 if(mapClone.containsKey(node))17 return mapClone.get(node);18 19 //if this node hasn‘t been cloned, we construct a new node copy20 UndirectedGraphNode copy = new UndirectedGraphNode(node.label);21 mapClone.put(node, copy);22 23 //clone all the neighbers of node24 for(UndirectedGraphNode n:node.neighbors){25 copy.neighbors.add(cloneNode(n));26 }27 return copy;28 }29 public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {30 return cloneNode(node);31 }32 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。