首页 > 代码库 > 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 node0to both nodes1and2. - Second node is labeled as
1. Connect node1to node2. - Third node is labeled as
2. Connect node2to node2(itself), thus forming a self-cycle.
Visually, the graph looks like the following:
1 / / 0 --- 2 / \_/
题目意思是克隆一张图。
我的解题思路是 先用bfs遍历原来的图，把label和节点加入到map中。
然后新建一个复制节点的map，遍历原来map，第一遍遍历新建节点 加入到新map中，第二遍把邻节点list加到新节点中。
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 private void bfs(UndirectedGraphNode node,HashMap<Integer, UndirectedGraphNode> visitedmap) {11 12 LinkedList<UndirectedGraphNode> tovisitList = new LinkedList<>();13 14 tovisitList.addLast(node);15 while (!tovisitList.isEmpty()) {16 UndirectedGraphNode first = tovisitList.getFirst();17 tovisitList.removeFirst();18 visitedmap.put(first.label, first);19 for (UndirectedGraphNode undirectedGraphNode : first.neighbors) {20 if (!visitedmap.containsKey(undirectedGraphNode.label)&&!tovisitList.contains(undirectedGraphNode)) {21 tovisitList.addLast(undirectedGraphNode);22 }23 }24 }25 26 }27 public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {28 if (node==null) {29 return null;30 }31 UndirectedGraphNode newGraph = new UndirectedGraphNode(node.label);32 if (node.neighbors.isEmpty()) {33 return newGraph;34 }35 HashMap<Integer, UndirectedGraphNode> visitedmap=new HashMap<>();36 HashMap<Integer, UndirectedGraphNode> copymap=new HashMap<>();37 bfs(node, visitedmap);38 for (Integer key : visitedmap.keySet()) {39 copymap.put(key, new UndirectedGraphNode(key));40 }41 for (Integer key : visitedmap.keySet()) {42 for (UndirectedGraphNode tnode : visitedmap.get(key).neighbors) {43 copymap.get(key).neighbors.add(copymap.get(tnode.label));44 }45 }46 return copymap.get(node.label);47 48 }49 50 51 }
LeetCode Clone Graph
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。