好贷网好贷款

LeetCode | Clone Graph

发布时间:2016-12-5 10:33:08 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"LeetCode | Clone Graph",主要涉及到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 node 0 to both nodes 1 and 2.Second node is labeled as 1. Connect node 1 to node 2.Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle. Visually, the graph looks like the following: 1 / \ / \ 0 --- 2 / \ \_/ 分析 这题与Copy with Random Pointer思路一致,都是通过纪录原节点和新节点的映射关系来构建新的数据结构,只要正确遍历完所有节点即可,如下代码中采用BFS进行遍历。 代码 import java.util.ArrayList; import java.util.HashMap; import java.util.Map; import java.util.Stack; public class CloneGraph { class UndirectedGraphNode { int label; ArrayList<UndirectedGraphNode> neighbors; UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); } } public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { if (node == null) { return null; } Stack<UndirectedGraphNode> stack = new Stack<UndirectedGraphNode>(); Map<Integer, UndirectedGraphNode> map = new HashMap<Integer, UndirectedGraphNode>(); UndirectedGraphNode root = new UndirectedGraphNode(node.label); map.put(node.label, root); stack.push(node); while (!stack.isEmpty()) { UndirectedGraphNode v = stack.pop(); UndirectedGraphNode newV = map.get(v.label); ArrayList<UndirectedGraphNode> newNeighbors = new ArrayList<UndirectedGraphNode>(); for (UndirectedGraphNode w : v.neighbors) { UndirectedGraphNode newW = null; if (map.containsKey(w.label)) { newW = map.get(w.label); } else { newW = new UndirectedGraphNode(w.label); map.put(w.label, newW); stack.push(w); } newNeighbors.add(newW); } newV.neighbors = newNeighbors; } return root; } }

上一篇:JNDI之我见
下一篇:关于“IOS6_内置字体库下载”的文章网址

相关文章

相关评论