内容简介:Given the head of a graph, return a deep copy (clone) of the graph. Each node in the graph contains a label (int) and a list (List[UndirectedGraphNode]) of its neighbors. There is an edge between the given node and each of the nodes in its neighbors.OJ's u
Given the head of a graph, return a deep copy (clone) of the graph. Each node in the graph contains a label (int) and a list (List[UndirectedGraphNode]) of its neighbors. There is an edge between the given node and each of the nodes in its neighbors.
OJ's undirected graph serialization (so you can understand error output):
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 / \ \_/
Note: The information about the tree serialization is only meant so that you can understand error output if you get a wrong answer. You don't need to understand the serialization to solve the problem.
难度:medium
题目:给定一图的头结点,返回其深拷贝。每个结点包含一个标签及一组邻结点。在给定的结点与其邻结点之间都有一边。
思路:BFS
Runtime: 6 ms, faster than 19.61% of Java online submissions for Clone Graph.
Memory Usage: 37.9 MB, less than 95.96% of Java online submissions for Clone Graph.
/** * Definition for undirected graph. * class UndirectedGraphNode { * int label; * List<UndirectedGraphNode> neighbors; * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); } * }; */ public class Solution { public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { if (null == node) { return null; } Queue<UndirectedGraphNode> queue = new LinkedList<>(); queue.add(node); Map<UndirectedGraphNode, UndirectedGraphNode> nodes = new HashMap<>(); while (!queue.isEmpty()) { UndirectedGraphNode tNode = queue.poll(); nodes.put(tNode, new UndirectedGraphNode(tNode.label)); for (UndirectedGraphNode n: tNode.neighbors) { if (!nodes.containsKey(n)) { queue.add(n); } } } for (Map.Entry<UndirectedGraphNode, UndirectedGraphNode> e: nodes.entrySet()) { UndirectedGraphNode copyNode = e.getValue(); for (UndirectedGraphNode n : e.getKey().neighbors) { copyNode.neighbors.add(nodes.get(n)); } } return nodes.get(node); } }
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Code Reading
Diomidis Spinellis / Addison-Wesley Professional / 2003-06-06 / USD 64.99
This book is a unique and essential reference that focuses upon the reading and comprehension of existing software code. While code reading is an important task faced by the vast majority of students,......一起来看看 《Code Reading》 这本书的介绍吧!