題目:
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 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:
Solution
**S1. BFS get all nodes. (version with no level order)
S2. Use a Hashmap and store the mapping relationship btw old---new nodes.(create new node based on old one)
S3. get the neighbor info and connect the edge based on hashmap.**
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { if (node == null) { return node; } // use bfs algorithm to traverse the graph and get all nodes. ArrayListnodes = getNodes(node); // copy nodes, store the old->new mapping information in a hash map HashMap mapping = new HashMap<>(); for (UndirectedGraphNode n : nodes) { mapping.put(n, new UndirectedGraphNode(n.label)); } // copy neighbors(edges) for (UndirectedGraphNode n : nodes) { UndirectedGraphNode newNode = mapping.get(n); for (UndirectedGraphNode neighbor : n.neighbors) { UndirectedGraphNode newNeighbor = mapping.get(neighbor); newNode.neighbors.add(newNeighbor); } } return mapping.get(node); } private ArrayList getNodes(UndirectedGraphNode node) { Queue queue = new LinkedList (); HashSet set = new HashSet<>(); queue.offer(node); set.add(node); while (!queue.isEmpty()) { UndirectedGraphNode head = queue.poll(); for (UndirectedGraphNode neighbor : head.neighbors) { if(!set.contains(neighbor)){ set.add(neighbor); queue.offer(neighbor); } } } return new ArrayList (set); }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/66433.html
摘要:我們只要保證,對于第一次遇到的圖節點,我們都會建立一個克隆節點,并在哈希表映射起來就行了。所以只要哈希表中有這個圖節點,就說明我們之前已經將該圖節點放入隊列了,就不需要再處理了。 Clone Graph Clone an undirected graph. Each node in the graph contains a label and a list of its neighb...
摘要:開始看這道題目的時候,沒有看懂和的作用。然后對這個放入的結點開始操作遍歷的所有,當前遍歷到的的叫做。當完成,則中沒有新的結點了,退出循環。返回在中更新過的,結束。 Problem Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors. We use #...
摘要:解題思路涉及到圖的遍歷無非就是深度優先搜索廣度優先搜索,可以先看前幾日的這篇文章就需要借助隊列實現,可以借助棧也可以直接用遞歸實現。 題目: 給定無向連通圖中一個節點的引用,返回該圖的深拷貝(克隆)。圖中的每個節點都包含它的值 val(Int) 和其鄰居的列表(list[Node])。 Given a reference of a node in a connected undirec...
摘要:遍歷路徑,找到所有可以到達終點節點的路徑就是結果。提示中說保證輸入為有向無環圖,所以我們可以認為節點間一定有著某種排列的順序,從頭到尾怎樣可以有最多的路徑呢,那就是在保證沒有環路的情況下,所有節點都盡可能多的連接著其他節點。 ...
摘要:由于是基于的,因此對有一定的了解會對的理解和使用有較大幫助。由于是基于的,因此有視圖和模型的概念。掛載的元素關聯聲明的元素的概念,就是圖形顯示的主體,可以有各種不同的形狀,預設有常用的矩形橢圓平行四邊形等。 一、jointJS簡介 jointJS是一個基于svg的圖形化工具庫,在畫布上畫出支持拖動的svg圖形,而且可以導出JSON,也能通過JSON配置導入直接生成圖形。 可以基于joi...
閱讀 3205·2021-11-17 09:33
閱讀 3288·2021-11-15 11:37
閱讀 2950·2021-10-19 11:47
閱讀 3199·2019-08-29 15:32
閱讀 1002·2019-08-29 15:27
閱讀 1526·2019-08-29 13:15
閱讀 932·2019-08-29 12:47
閱讀 2023·2019-08-29 11:30