資訊專欄INFORMATION COLUMN
題目：
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.
ArrayList nodes = 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);
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66433.html
摘要：我們只要保證，對(duì)于第一次遇到的圖節(jié)點(diǎn)，我們都會(huì)建立一個(gè)克隆節(jié)點(diǎn)，并在哈希表映射起來(lái)就行了。所以只要哈希表中有這個(gè)圖節(jié)點(diǎn)，就說(shuō)明我們之前已經(jīng)將該圖節(jié)點(diǎn)放入隊(duì)列了，就不需要再處理了。 Clone Graph Clone an undirected graph. Each node in the graph contains a label and a list of its neighb...
摘要：開始看這道題目的時(shí)候，沒(méi)有看懂和的作用。然后對(duì)這個(gè)放入的結(jié)點(diǎn)開始操作遍歷的所有，當(dāng)前遍歷到的的叫做。當(dāng)完成，則中沒(méi)有新的結(jié)點(diǎn)了，退出循環(huán)。返回在中更新過(guò)的，結(jié)束。 Problem Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors. We use #...
摘要：解題思路涉及到圖的遍歷無(wú)非就是深度優(yōu)先搜索廣度優(yōu)先搜索，可以先看前幾日的這篇文章就需要借助隊(duì)列實(shí)現(xiàn)，可以借助棧也可以直接用遞歸實(shí)現(xiàn)。 題目： 給定無(wú)向連通圖中一個(gè)節(jié)點(diǎn)的引用，返回該圖的深拷貝（克隆）。圖中的每個(gè)節(jié)點(diǎn)都包含它的值 val（Int） 和其鄰居的列表（list[Node]）。 Given a reference of a node in a connected undirec...
摘要：遍歷路徑，找到所有可以到達(dá)終點(diǎn)節(jié)點(diǎn)的路徑就是結(jié)果。提示中說(shuō)保證輸入為有向無(wú)環(huán)圖，所以我們可以認(rèn)為節(jié)點(diǎn)間一定有著某種排列的順序，從頭到尾怎樣可以有最多的路徑呢，那就是在保證沒(méi)有環(huán)路的情況下，所有節(jié)點(diǎn)都盡可能多的連接著其他節(jié)點(diǎn)。 ...
摘要：由于是基于的，因此對(duì)有一定的了解會(huì)對(duì)的理解和使用有較大幫助。由于是基于的，因此有視圖和模型的概念。掛載的元素關(guān)聯(lián)聲明的元素的概念，就是圖形顯示的主體，可以有各種不同的形狀，預(yù)設(shè)有常用的矩形橢圓平行四邊形等。 一、jointJS簡(jiǎn)介 jointJS是一個(gè)基于svg的圖形化工具庫(kù)，在畫布上畫出支持拖動(dòng)的svg圖形，而且可以導(dǎo)出JSON，也能通過(guò)JSON配置導(dǎo)入直接生成圖形。 可以基于joi...
閱讀 3219·2021-11-17 09:33
閱讀 3299·2021-11-15 11:37
閱讀 2966·2021-10-19 11:47
閱讀 3215·2019-08-29 15:32
閱讀 1019·2019-08-29 15:27
閱讀 1539·2019-08-29 13:15
閱讀 943·2019-08-29 12:47
閱讀 2036·2019-08-29 11:30
