摘要:開始看這道題目的時候,沒有看懂和的作用。然后對這個放入的結點開始操作遍歷的所有,當前遍歷到的的叫做。當完成,則中沒有新的結點了,退出循環。返回在中更新過的,結束。
Problem
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
return a deep copied graph.
ExampleHow we serialize an undirected graph.
Nodes are labeled uniquely.
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
開始看這道題目的時候,沒有看懂queue和hashmap的作用。
復制一個無向圖,先分析圖的結構:label相當于圖結點的value,而neighbors相當于圖結點的所有next。然后考慮用什么方式復制:用queue用來標記當前正在復制的或已經復制過的結點cur,而hashmap用來進行對新建無向圖結點root進行復制label和neighbors的操作。首先,從node結點開始,放入queue。然后對這個放入queue的結點cur開始操作:遍歷cur的所有neighbors,當前遍歷到的的neighbors叫做next。若map中不存在這個點,即沒有被復制過,就在map中復制這個結點next的label,同時存入queue以便在下次循環取出并復制其neighbors;無論map中包不包含這個neighbors結點next,都要將next加入map中對應新建結點root的neighbors。當BFS完成,則queue中沒有新的結點了,退出while循環。返回在map中更新過的root,結束。
map.get(cur).neighbors.add(map.get(next));
這一句可以理解為,在for循環對cur的neighbors的遍歷中,先在HashMap里的root中建立新結點next,再將next放進root的結點cur的neighbors里。
// Definition for undirected graph. class UndirectedGraphNode { int label;ArrayListneighbors; UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList (); } }
public class Solution { public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { if (node == null) return null; UndirectedGraphNode root = new UndirectedGraphNode(node.label);//復制根節點 QueueUpdate 2018-9 BFSqueue = new LinkedList<>(); Map map = new HashMap<>(); queue.offer(node);//queue放入根結點 map.put(node, root);//map放入根結點和它的復制結點 while (!queue.isEmpty()) { UndirectedGraphNode cur = queue.poll();//取出queue中(同一層)的結點進行BFS for (UndirectedGraphNode n: cur.neighbors) { //對沒有復制過的結點進行復制,并將這個結點放入queue if (!map.containsKey(n)) { map.put(n, new UndirectedGraphNode(n.label)); queue.offer(n); } //連接復制結點和復制neighbor結點 map.get(cur).neighbors.add(map.get(n)); } } return root; } }
public class Solution { public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { if (node == null) return node; Mapmap = new HashMap<>(); map.put(node, new UndirectedGraphNode(node.label)); // : <原結點, 復制結點> Queue queue = new LinkedList<>(); queue.offer(node); //copy過的結點存入queue,以繼續遍歷其neighbor結點 while (!queue.isEmpty()) { UndirectedGraphNode cur = queue.poll(); //取出copy過的結點,繼續復制其所有neighbor結點 for (UndirectedGraphNode neighbor: cur.neighbors) { if (!map.containsKey(neighbor)) { //若結點未復制過,copy后存入queue map.put(neighbor, new UndirectedGraphNode(neighbor.label)); queue.offer(neighbor); } map.get(cur).neighbors.add(map.get(neighbor)); //將每個copied neighbor存入copied parent node } } return map.get(node); //返回copied根節點 } }
DFS
public class Solution { public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { Mapmap = new HashMap<>(); return cloneNode(node, map); } private UndirectedGraphNode cloneNode(UndirectedGraphNode node, Map map) { if (node == null) return node; if (map.containsKey(node)) { return map.get(node); } else { UndirectedGraphNode nodeCopy = new UndirectedGraphNode(node.label); map.put(node, nodeCopy); for (UndirectedGraphNode child : node.neighbors) { nodeCopy.neighbors.add(cloneNode(child, map)); } return nodeCopy; } } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/65729.html
摘要:解題思路涉及到圖的遍歷無非就是深度優先搜索廣度優先搜索,可以先看前幾日的這篇文章就需要借助隊列實現,可以借助棧也可以直接用遞歸實現。 題目: 給定無向連通圖中一個節點的引用,返回該圖的深拷貝(克隆)。圖中的每個節點都包含它的值 val(Int) 和其鄰居的列表(list[Node])。 Given a reference of a node in a connected undirec...
1. 說明 本文所有的算法嚴格按照《算法導論》,本文將詳細的對BFS和DFS進行分析,并提供算法的 js 實現,同時會對創建鏈表的方式進行優化 2. 圖的表示 圖的表示分為對頂點集 V 的表示和對邊集 E 的表示,這里的重點是如何表示邊,邊的表示分為鄰接矩陣和鄰接鏈表這兩種表示方法,鄰接矩陣適合表示邊稠密的圖,其消耗空間為|V|*|V|,如果是無向圖,則可以用上三角矩陣或者下三角矩陣來表示,是空間...
摘要:但是一個偏序關系,如果我們默認,先出現的排在前面,那么我們就能比較,的關系了。對于算法的每個節點,我們都有一個發現時間,一個訪問時間,當運行完成時,對于圖中的任意一條邊,都有所以拓撲排序的次序與頂點的完成時間恰好相反。 1. 偏序和全序的概念 1.1. 偏序 設R是集合A上的一個二元關系,若R滿足下列三個性質則稱R為A上的偏序關系自反性:對任意x∈A,有∈R反對稱性:對任意的x,y∈A...
Problem There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up, down, left or right, but it wont stop rolling until hitting a wall. When the ball sto...
摘要:生成樹和最小生成樹的概念設圖連通,則生成樹包含圖中的所有節點,及條邊的連通圖,一個圖的生成樹可以有多顆最小生成樹最小權重生成樹,在生成樹的概念上加一個限制條件,即生成樹的所有邊的權值總和最小的樹,最小生成樹也可以有多顆求解最小生成樹的通用 1. 生成樹和最小生成樹的概念 設圖G(V,E)連通,則生成樹:包含圖G(V,E)中的所有節點,及|V|-1條邊的連通圖,一個圖的生成樹可以有多顆最...
閱讀 1854·2023-04-25 23:28
閱讀 563·2023-04-25 22:49
閱讀 2241·2021-09-27 13:34
閱讀 5158·2021-09-22 15:09
閱讀 3609·2019-08-30 12:52
閱讀 2740·2019-08-29 15:26
閱讀 659·2019-08-29 11:12
閱讀 2190·2019-08-26 12:24