CloneGraph题目描述：给定一个无向连通图中节点的引用，请返回该图的深层副本（克隆）。图中的每个节点都包含它的值val(int)和它的邻居列表(list[Node])。例子见LeetCode官网。来源：LeetCode链接：https://leetcode-cn.com/probl...版权归LeetCode所有。商业转载请联系官方授权，非商业转载请注明出处。方案一：深度优先遍历首先，如果当前节点为空，不做任何处理，直接返回。否则，使用Map(visited)存储处理过的图节点和对应的克隆节点。递归处理过程是这样的：判断当前节点是否在visited中，如果是就说明已经处理过了，然后直接从visited中取出一个当前节点的clone返回。否则，根据当前节点克隆一个新的克隆节点，并将新克隆节点的邻居节点初始化为空，然后将当前节点和新的克隆节点加入visited；然后递归处理当前节点的邻居节点。最后，返回当前节点的克隆节点。方案二：广度优先遍历也是一样，首先如果当前节点为空，不做任何处理，直接返回。否则，还需要初始化一个被访问的Map，用来存放处理过的图节点和对应的克隆节点。首先将当前节点和当前节点克隆的节点添加到visited，然后将当前节点添加到队列中。然后处理队列中的节点，知道队列不为空，处理过程如下：取出队列的头节点为curNode；遍历并处理curNode节点的邻居节点；如果当前邻居节点没有被访问过，则将其和对应的克隆节点加入到已访问过的队列中；然后将当前邻居节点的克隆节点添加到curNode的克隆节点的邻居节点列表中。最后，返回原始节点的克隆节点。注：我对图相关的算法还是不太了解，多多学习。importcom.kaesar.leetcode.GraphNode;importjava.util.*;publicclassLeetCode_133{privatestaticMapvisited=newHashMap<>();/***深度优先遍历**@paramnodecurrentNode*@return*/publicstaticGraphNodecloneGraph(GraphNodenode){if(node==null){returnnode;}//如果该节点已经被访问过，则直接从哈希表中取出对应的克隆节点returnif(visited.containsKey(node)){returnvisited.get(node);}//克隆当前节点GraphNodecloneNode=newGraphNode(node.val,newArrayList<>());//在哈希表中访问的存储.put(node,cloneNode);//递归处理当前节点的邻居节点for(GraphNodeneighbor:node.neighbors){cloneNode.neighbors.add(cloneGraph(neighbor));}返回克隆节点；}/***广度优先遍历**@paramnode当前节点*@return*/publicstaticGraphNodecloneGraph2(GraphNodenode){if(node==null){返回节点；}HashMapvisited=newHashMap<>();队列queue=newLinkedList<>();//将当前节点加入队列queue.add(node);//克隆第一个节点并将其存储在哈希表中visited.put(node,newGraphNode(node.val,newArrayList<>()));//广度优先遍历while(!queue.isEmpty()){//取出队列的头节点GraphNodecurNode=queue.remove();//遍历当前节点的邻居节点for(GraphNodeneighbor:curNode.neighbors){if(!visited.containsKey(neighbor)){visited.put(neighbor,newGraphNode(neighbor.val,newArrayList<>()));//将邻居节点加入队列queue.add(neighbor);}//更新当前节点的邻居节点列表visited.get(curNode).neighbors.add(visited.get(neighbor));}}返回visited.get(node);}publicstaticvoidmain(String[]args){}}【每日留言】自己动手，丰衣足食！
