Clone Graph

xioqua 發(fā)布于2019-08-14 17:07 / 3344人閱讀

題目：
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);
    }

GPU云服務器云服務器 graph graph編程語言 Clone git clone

文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://m.hztianpu.com/yun/66433.html

[Leetcode] Clone Graph 復制圖

摘要：我們只要保證，對于第一次遇到的圖節(jié)點，我們都會建立一個克隆節(jié)點，并在哈希表映射起來就行了。所以只要哈希表中有這個圖節(jié)點，就說明我們之前已經(jīng)將該圖節(jié)點放入隊列了，就不需要再處理了。 Clone Graph Clone an undirected graph. Each node in the graph contains a label and a list of its neighb...

xietao3 2019-08-14 12:29 評論0 收藏0
[LintCode/LeetCode] Clone Graph [BFS/DFS]

摘要：開始看這道題目的時候，沒有看懂和的作用。然后對這個放入的結點開始操作遍歷的所有，當前遍歷到的的叫做。當完成，則中沒有新的結點了，退出循環(huán)。返回在中更新過的，結束。 Problem Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors. We use #...

fredshare 2019-08-14 15:23 評論0 收藏0
LeetCode 133：克隆圖 Clone Graph

摘要：解題思路涉及到圖的遍歷無非就是深度優(yōu)先搜索廣度優(yōu)先搜索，可以先看前幾日的這篇文章就需要借助隊列實現(xiàn)，可以借助棧也可以直接用遞歸實現(xiàn)。題目：給定無向連通圖中一個節(jié)點的引用，返回該圖的深拷貝（克?。D中的每個節(jié)點都包含它的值 val（Int）和其鄰居的列表（list[Node]）。 Given a reference of a node in a connected undirec...

Simon 2019-08-19 10:35 評論0 收藏0
【算法】劍指 Offer II 110. 所有路徑｜797. 所有可能的路徑（多語言實現(xiàn)）

摘要：遍歷路徑，找到所有可以到達終點節(jié)點的路徑就是結果。提示中說保證輸入為有向無環(huán)圖，所以我們可以認為節(jié)點間一定有著某種排列的順序，從頭到尾怎樣可以有最多的路徑呢，那就是在保證沒有環(huán)路的情況下，所有節(jié)點都盡可能多的連接著其他節(jié)點。 ...

wangdai 2021-11-23 09:51 評論0 收藏0
jointJS系列之一：jointJS的的初步使用

摘要：由于是基于的，因此對有一定的了解會對的理解和使用有較大幫助。由于是基于的，因此有視圖和模型的概念。掛載的元素關聯(lián)聲明的元素的概念，就是圖形顯示的主體，可以有各種不同的形狀，預設有常用的矩形橢圓平行四邊形等。一、jointJS簡介 jointJS是一個基于svg的圖形化工具庫，在畫布上畫出支持拖動的svg圖形，而且可以導出JSON，也能通過JSON配置導入直接生成圖形。可以基于joi...

amuqiao 2019-08-23 10:56 評論0 收藏0