昆明cms建站模板,低价做网站,wordpress调用面包屑,58同城最新招聘网找工作招聘信息克隆图
力扣链接#xff1a;133. 克隆图
题目描述
给你无向 连通 图中一个节点的引用#xff0c;请你返回该图的 深拷贝#xff08;克隆#xff09;。
示例 分析
对于一张图而言#xff0c;它的深拷贝即构建一张与原图结构#xff0c;值均一样的图#xff0c;但是…克隆图
力扣链接133. 克隆图
题目描述
给你无向 连通 图中一个节点的引用请你返回该图的 深拷贝克隆。
示例 分析
对于一张图而言它的深拷贝即构建一张与原图结构值均一样的图但是其中的节点不再是原来图节点的引用。因此为了深拷贝出整张图我们需要知道整张图的结构以及对应节点的值。
由于题目只给了我们一个节点的引用因此为了知道整张图的结构以及对应节点的值我们需要从给定的节点出发进行「图的遍历」并在遍历的过程中完成图的深拷贝。
为了防止多次遍历同一个节点陷入死循环我们需要用一种数据结构记录已经被克隆过的节点。
深度优先搜索 class Solution {private HashMapNode, Node visited new HashMap();public Node cloneGraph(Node node) {if(node null) return node;if(visited.containsKey(node)) return visited.get(node);Node cloneNode new Node(node.val, new ArrayList());visited.put(node, cloneNode);for(Node neighbor : node.neighbors) {cloneNode.neighbors.add(cloneGraph(neighbor));}return cloneNode;}
}广度优先搜索
class Solution {public Node cloneGraph(Node node) {if(node null) return node;HashMapNode, Node visited new HashMap();LinkedListNode queue new LinkedListNode();queue.add(node);visited.put(node, new Node(node.val, new ArrayList()));while(!queue.isEmpty()) {Node n queue.remove();for(Node neighbor : n.neighbors) {if(!visited.containsKey(neighbor)) {visited.put(neighbor, new Node(neighbor.val, new ArrayList()));queue.add(neighbor);}visited.get(n).neighbors.add(visited.get(neighbor));}}return visited.get(node);}
}
