原题链接:http://oj.leetcode.com/problems/clone-graph/这道题是LeetCode中为数不多的关于图的题目,不过这道题还是比较基础,就是考察图非常经典的方法:深度优先搜索和广度优先搜索。这道题用两种方法都可以解决,因为只是一个图的复制,用哪种遍历方式都可以。具体细节就不多说了,因为两种方法太常见了。这里恰好可以用旧结点和新结点的HashMap来做visited的记录。下面是广度优先搜索的代码:public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if(node==null)
return null;
LinkedList<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
UndirectedGraphNode copy = new UndirectedGraphNode(node.label);
map.put(node,copy);
queue.offer(node);
while(!queue.isEmpty())
{
UndirectedGraphNode cur = queue.poll();
for(int i=0;i<cur.neighbors.size();i++)
{
if(!map.containsKey(cur.neighbors.get(i)))
{
copy = new UndirectedGraphNode(cur.neighbors.get(i).label);
map.put(cur.neighbors.get(i),copy);
queue.offer(cur.neighbors.get(i));
}
map.get(cur).neighbors.add(map.get(cur.neighbors.get(i)));
}
}
return map.get(node);
}
深度优先搜索的代码如下:public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if(node == null)
return null;
LinkedList<UndirectedGraphNode> stack = new LinkedList<UndirectedGraphNode>();
HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
stack.push(node);
UndirectedGraphNode copy = new UndirectedGraphNode(node.label);
map.put(node,copy);
while(!stack.isEmpty())
{
UndirectedGraphNode cur = stack.pop();
for(int i=0;i<cur.neighbors.size();i++)
{
if(!map.containsKey(cur.neighbors.get(i)))
{
copy = new UndirectedGraphNode(cur.neighbors.get(i).label);
map.put(cur.neighbors.get(i),copy);
stack.push(cur.neighbors.get(i));
}
map.get(cur).neighbors.add(map.get(cur.neighbors.get(i)));
}
}
return map.get(node);
}
当然深度优先搜索也可以用递归来实现,代码如下:public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if(node == null)
return null;
HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
UndirectedGraphNode copy = new UndirectedGraphNode(node.label);
map.put(node,copy);
helper(node,map);
return copy;
}
private void helper(UndirectedGraphNode node, HashMap<UndirectedGraphNode, UndirectedGraphNode> map)
{
for(int i=0;i<node.neighbors.size();i++)
{
UndirectedGraphNode cur = node.neighbors.get(i);
if(!map.containsKey(cur))
{
UndirectedGraphNode copy = new UndirectedGraphNode(cur.label);
map.put(cur,copy);
helper(cur,map);
}
map.get(node).neighbors.add(map.get(cur));
}
}
这几种方法的时间复杂度都是O(n)(每个结点访问一次),而空间复杂度则是栈或者队列的大小加上HashMap的大小,也不会超过O(n)。图的两种遍历方式是比较经典的问题了,虽然在面试中出现的不多,但是还是有可能出现的,而且如果出现了就必须做好,所以大家还是得好好掌握哈。
分享到:
相关推荐
leetcode CloneGraph java 源代码
git@github.com:fakeYanss/leetcode-solution.git cd leetcode # on linux & mac ./gradlew # on windows gradlew.bat 项目结构: 内层结构按题目类型划分,并不十分严谨,可能按数据结构分类和按算法分类会有部分...
133.Clone_Graph_克隆图【LeetCode单题讲解系列】
leetcode 分类 Leetcode 介绍 leetcode个人题解,根据leetcode给的标签进行分类,按照数据结构对题目...graph:图论 greedy:贪心算法 recursion:递归算法 sort:排序算法 heap: 堆的应用题解 安装教程 clone IDEA JDK 8
Clone Graph, medium --- 类似于#138 207,课程表,中等 210 课程表 II,中等 261,图有效树,中等 310,最小高度树,中等 323,无向图中连通分量的数量,中等 444,序列重建,中 第二周——堆 215,数组中的第 K 个...
Clone_Graph 组合_总和 Counting_Carry_Digits 平等的 First_Missing_Positive Generate_All_Parenthesis_2 实现_StrStr Largest_Distance_Between_Nodes_Of_A_Tree Largest_Rectangle_In_Histogram Least_C
与大家分享我学习算法的一些经历。这个项目不定期更新。数组/链表:树相关:AVLTree 平衡二叉搜索树...BFSGraph 图BFS模板Dijkstra 寻求最短路SwimmingCrossSea 漂洋过海CloneGraph (leetcode 133)字符串相关:Reve
图形**** ****BFS class Solution { public Node cloneGraph ( Node node ) { if (node == null ) { return null ; } Map< Node> map = new HashMap<> (); Queue< Node> queue = new LinkedList<> (); queue ....
存储库会定期更新,因此请确保提取代码git pull组织这些问题按其来源的主要主题划分问题陈述在代码顶部被注释掉LeetCode问题被命名为leetcode_(问题编号)_(问题标题),并且仅提供Solution类其他问题仅通过标题...
Clone Graph 位操作 Reverse Bits Repeated DNA Sequences Number of 1 Bits Gray Code Single Number Single Number II Single Number III Power of Two Missing Number Maximum Product of Word Lengths Bitwise ...