首页 > 代码库 > [leecode]Clone Graph
[leecode]Clone Graph
Clone Graph
Clone an undirected graph. Each node in the graph contains a
labeland 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
#.
- 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 / \_/
算法分析：
BFS的变种，维护一个map来记录已经生成的copy node，如果已经生成，则直接从map中取就行了，否则需要new出一个新的。
维护一个set来记录在queue中，或者已经出queue的点（其实没有必要用set的，直接可以在queue里查询的，但是考虑到效率，还是用了set，而且只记录label，空间也很省）
代码如下：
1 public class Solution { 2 public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { 3 if(node == null) return null; 4 Queue<UndirectedGraphNode> q = new LinkedList<UndirectedGraphNode>(); 5 Set<Integer> set = new HashSet<Integer>(); 6 Map<Integer,UndirectedGraphNode> map = new HashMap<Integer,UndirectedGraphNode>(); 7 set.add(node.label); 8 q.offer(node); 9 map.put(node.label,new UndirectedGraphNode(node.label));10 while(!q.isEmpty()){11 UndirectedGraphNode tem = q.poll();12 UndirectedGraphNode copy = map.get(tem.label);13 List<UndirectedGraphNode> neighbors = tem.neighbors;14 for(UndirectedGraphNode neighbor : neighbors){15 if(!set.contains(neighbor.label)){16 set.add(neighbor.label);17 q.offer(neighbor);18 }19 if(!map.containsKey(neighbor.label)){20 UndirectedGraphNode copyNeighbor = new UndirectedGraphNode(neighbor.label);21 map.put(neighbor.label,copyNeighbor);22 copy.neighbors.add(copyNeighbor);23 }else{24 copy.neighbors.add(map.get(neighbor.label));25 }26 }27 }28 return map.get(node.label);29 }30 }
[leecode]Clone Graph
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。