[Leetcode] Clone Graph 復制圖

xietao3 發布于2019-08-14 12:29 / 2042人閱讀

摘要：我們只要保證，對于第一次遇到的圖節點，我們都會建立一個克隆節點，并在哈希表映射起來就行了。所以只要哈希表中有這個圖節點，就說明我們之前已經將該圖節點放入隊列了，就不需要再處理了。

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 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
     / 
     \_/

哈希表法 復雜度

時間 O(N) 空間 O(N)

思路

廣度優先搜索，同時用一個哈希表，將新舊節點映射起來。這樣我們第一次遍歷到的節點，我們會新建一個節點并映射到哈希表中。當以后再遍歷到這個節點時，我們可以直接用哈希表取出它對應的新節點。我們只要保證，對于第一次遇到的圖節點，我們都會建立一個克隆節點，并在哈希表映射起來就行了。

注意

這里我們并不需要維護一個visited的集合，為什么呢？因為每次我們遇到一個之前沒見過圖節點，我們都會給它建立一個克隆節點，然后在哈希表中映射起來，并把這個圖節點也放入隊列中。所以只要哈希表中有這個圖節點，就說明我們之前已經將該圖節點放入隊列了，就不需要再處理了。不過還是要把該圖節點的克隆節點放入父克隆節點的鄰居中。

代碼

public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node == null) return null;
        Queue q = new LinkedList();
        Map map = new HashMap();
        UndirectedGraphNode root = new UndirectedGraphNode(node.label);
        map.put(node, root);
        q.offer(node);
        while(!q.isEmpty()){
            UndirectedGraphNode curr = q.poll();
            // 將curr舊節點的鄰居節點都加入curr的新節點
            for(UndirectedGraphNode oldNeighbor : curr.neighbors){
                // 判斷是否已經生成過該鄰居節點的新節點
                if(!map.containsKey(oldNeighbor)){
                    // 如果是第一次生成該新節點，將其加入隊列中
                    map.put(oldNeighbor, new UndirectedGraphNode(oldNeighbor.label));
                    q.offer(oldNeighbor);
                }
                // 將新鄰居加入新curr節點的neighbors中
                map.get(curr).neighbors.add(map.get(oldNeighbor));
            }
        }
        return root;
    }
}

GPU云服務器云服務器 graph LeetCode graph編程語言 LeetCode_String

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64503.html

[LintCode/LeetCode] Clone Graph [BFS/DFS]

摘要：開始看這道題目的時候，沒有看懂和的作用。然后對這個放入的結點開始操作遍歷的所有，當前遍歷到的的叫做。當完成，則中沒有新的結點了，退出循環。返回在中更新過的，結束。 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

摘要：解題思路涉及到圖的遍歷無非就是深度優先搜索廣度優先搜索，可以先看前幾日的這篇文章就需要借助隊列實現，可以借助棧也可以直接用遞歸實現。題目：給定無向連通圖中一個節點的引用，返回該圖的深拷貝（克隆）。圖中的每個節點都包含它的值 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. 所有可能的路徑（多語言實現）

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

wangdai 2021-11-23 09:51 評論0 收藏0
[Leetcode] Alien Dictionary 外文字典

摘要：拓撲排序復雜度時間空間思路首先簡單介紹一下拓撲排序，這是一個能夠找出有向無環圖順序的一個方法假設我們有條邊，先將每個節點的計數器初始化為。最后，我們開始拓撲排序，從計數器為的字母開始廣度優先搜索。 Alien Dictionary There is a new alien language which uses the latin alphabet. However, the ord...

pkhope 2019-08-14 12:38 評論0 收藏0
[Leetcode] Course Schedule 課程計劃

Course Schedule I There are a total of n courses you have to take, labeled from 0 to n - 1.Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is e...

Amio 2019-08-14 12:40 評論0 收藏0