首页 > 代码库 > 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 / \_/
Leetcode里关于图的题其实并不多,这道题就是其中之一。DFS深度优先搜索和BFS广度优先搜索都可以做,遍历完原图的所有节点。这道题的难点在于neighbour关系的拷贝:原图中某一个点跟一些点具有neighbour关系,那么该点的拷贝也要与上述那些点的拷贝具有neighbour关系。那么,就需要很灵活地通过一个点访问该点的拷贝,最好的办法就是把该点与该点的拷贝存入一个HashMap。这样做还有一个好处,就是帮我们剩下了一个visited数组,我们可以用这个HashMap来知道哪些点我是访问过的。
方法是用BFS做的:
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 public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {11 if (node == null) return null;12 HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();13 LinkedList<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();14 queue.offer(node);15 UndirectedGraphNode copy = new UndirectedGraphNode(node.label);16 map.put(node, copy);17 while (!queue.isEmpty()) {18 UndirectedGraphNode cur = queue.poll();19 for (int i=0; i<cur.neighbors.size(); i++) {20 if (!map.containsKey(cur.neighbors.get(i))) {21 queue.offer(cur.neighbors.get(i));22 UndirectedGraphNode neighborCopy = new UndirectedGraphNode(cur.neighbors.get(i).label);23 map.put(cur.neighbors.get(i), neighborCopy);24 }25 map.get(cur).neighbors.add(map.get(cur.neighbors.get(i)));26 }27 }28 return map.get(node);29 }30 }
网上看了别人的解法:
用Stack写的DFS方法:
1 public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { 2 if(node == null) 3 return null; 4 LinkedList<UndirectedGraphNode> stack = new LinkedList<UndirectedGraphNode>(); 5 HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>(); 6 stack.push(node); 7 UndirectedGraphNode copy = new UndirectedGraphNode(node.label); 8 map.put(node,copy); 9 while(!stack.isEmpty())10 {11 UndirectedGraphNode cur = stack.pop();12 for(int i=0;i<cur.neighbors.size();i++)13 {14 if(!map.containsKey(cur.neighbors.get(i)))15 {16 copy = new UndirectedGraphNode(cur.neighbors.get(i).label);17 map.put(cur.neighbors.get(i),copy);18 stack.push(cur.neighbors.get(i));19 }20 map.get(cur).neighbors.add(map.get(cur.neighbors.get(i)));21 }22 }23 return map.get(node);24 }
用Recursion写的DFS方法:
1 public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { 2 if(node == null) 3 return null; 4 HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>(); 5 UndirectedGraphNode copy = new UndirectedGraphNode(node.label); 6 map.put(node,copy); 7 helper(node,map); 8 return copy; 9 }10 private void helper(UndirectedGraphNode node, HashMap<UndirectedGraphNode, UndirectedGraphNode> map)11 {12 for(int i=0;i<node.neighbors.size();i++)13 { 14 UndirectedGraphNode cur = node.neighbors.get(i);15 if(!map.containsKey(cur))16 {17 UndirectedGraphNode copy = new UndirectedGraphNode(cur.label);18 map.put(cur,copy);19 helper(cur,map);20 }21 map.get(node).neighbors.add(map.get(cur));22 }23 }
Leetcode: Clone Graph
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。