<output id="ilehw"><bdo id="ilehw"><nobr id="ilehw"></nobr></bdo></output>
        <dl id="ilehw"><font id="ilehw"></font></dl>
          1. 圖數據結構入門 已翻譯 100%

            祖沖之 投遞于 08/28 19:13 (共 14 段, 翻譯完成于 09-06)
            閱讀 1862
            收藏 74
            13
            加載中

            在這篇文章中,我們將探索像圖這樣的非線性數據結構。我們將介紹其核心概念和典型應用。

            你可能正在使用使用圖(和樹)數據結構的程序。比方說,你想知道你工作的地方和家之間的最短路徑,你可以使用圖算法來獲得答案!我們將探討這個和其他有趣的挑戰。

            在上一篇文章中,我們探索線性數據結構,如數組、鏈表、集合、棧等。這篇文章是建立在我們已學到的知識之上的。

            這篇文章是此教程系列的一部分:

            給初學者的數據結構及算法之路

            1. 算法時間復雜度及大O表示法簡介

            2. 每個程序員必知的三個時間復雜度

            3. 給初學者的數據結構:數組、哈希表以及鏈表

            4. 給初學者的數據結構之圖 <== 你在這里

            5. 給初學者的數據結構之樹

            6. 自平衡二叉搜索樹

            7. 附錄I: 遞歸算法分析

            以下是我們將在本文中介紹的操作的摘要:

             Adjacency ListAdjacency Matrix
            SpaceO(|V| + |E|)O(|V|2)
            addVertexO(1)O(|V|2)
            removeVertexO(|V| + |E|)O(|V|2)
            addEdgeO(1)O(1)
            removeEdge (using Array)O(|E|)O(1)
            removeEdge (using HashSet)O(1)O(1)
            getAdjacentsO(|E|)O(|V|)
            isAdjacent (using Array)O(|E|)O(1)
            isAdjacent (using HashSet)O(1)O(1)
            Tocy
            Tocy
            翻譯于 08/29 09:42
            0

            圖的基礎知識

            圖是一種數據結構,其中的節點可以具有零個或多個相鄰元素。兩個節點之間的連接稱為邊。 節點亦可稱為頂點。

            度是與頂點相關聯的邊的個數。例如,紫色頂點的度數為3,而藍色頂點度數為1.

            如果邊是雙向的,我們就有了一個無向圖。 但如果邊有方向,那么我們就有一個有向圖或簡單圖。 你可以將其視為單行道(有向)或雙向街道(無向)。

            頂點可以有關于自己的邊,例如藍的頂點,稱之為自循環。

            lnovonl
            lnovonl
            翻譯于 08/29 18:50
            0

            圖可以具有循環,這意味著如果要遍歷節點,則可以多次訪問同一節點。 沒有循環的圖稱為非循環圖。

            此外,非循環無向圖稱為樹。 我們將在下篇中深入講解樹。

            并非所有頂點都必須在圖中連接。 可以有孤立的節點甚至是分離的子圖。 如果所有節點都至少有一個邊,那么我們有一個連通圖。 當所有節點都連接到所有其他節點時,我們就有了完全圖。

            對于完全圖,每個節點必須有#nodes - 1個邊。 在前面的例子中,我們有7個頂點,因此每個節點有6個邊。

            lnovonl
            lnovonl
            翻譯于 08/29 18:58
            0

            圖的應用

            當邊具有已分配給它們的價值/費用時,我們說我們有一個加權圖。如果沒有加權值,我們可以假設它是1。

            加權圖具有許多應用場景,具體取決于你需要解決問題的域。僅舉幾例:

            • 航線交通 (見上圖)

              • 節點/頂點 = 機場

              • 邊 = 兩個機場之間的直接航班

              • 權重 = 兩個機場之間的里程數

            • GPS導航

              • 節點 = 道路交點

              • 邊 = 道路

              • 權重 = 兩個路口之間距離所需時間

            • 網絡路由

              • 節點 = 服務器

              • 邊 = 數據鏈路

              • 權重 = 連接速度

            通常,圖有很多現實世界的應用,比如: 

            • 電子電路

            • 航班預訂

            • 駕駛導航

            • 電性:信號塔頻率規劃

            • 社交網絡,比如,Facebook使用圖來實現朋友推薦

            • 推薦: Amazon/Netflix使用圖做產品/電影推薦

            • 圖有助于物流規劃設計

            我們剛剛學習了圖的基礎知識及其相關的一些應用場景。現在讓我們學習如何在代碼中表示圖。

            Tocy
            Tocy
            翻譯于 08/30 10:38
            0

            表示圖

            有兩種主要用于表示圖的方式:

            1. 鄰接表

            2. 鄰接矩陣

            讓我們用以下有向圖作為示例分析一下:

            此有向圖有4個節點。當一個頂點有指向自身的鏈接時(比如a)則稱之為自循環

            鄰接矩陣

            鄰接矩陣是一種使用二維數組(NxN矩陣)來表示圖的方式。針對頂點的相交的情況,如果二者是連接的,我們將添加1(或者其他權重),否則設置為0或-。

            使用之前的示例,我們可以構建以下鄰接矩陣:

            需要注意的是無向圖的鄰接矩陣總是以對角線為軸對稱的。然而,在有向圖中并不是如此(例如我們的示例中的有向圖)。正如你所看到的,該矩陣從水平和垂直方向列出了所有節點。如果連接比較少,我們稱之為稀疏圖;如果連接很多(接近最大連接數目),我們稱之為稠密圖。如果達到了所有可能的連接,我們就擁有了完全圖。

            查找兩個頂點之間的時間復雜度如何呢?

            在鄰接矩陣中查詢兩個頂點是否相連的復雜度是O(1).

            空間復雜度如何呢?

            將圖保存為鄰接矩陣的空間復雜度是O(n2),其中n是頂點的數目。也可表示為 O(|V|2)。

            添加一個頂點的運行時間如何呢?

            頂點被保存在VxV的矩陣中。因此,每次添加頂點時,矩陣必須被重構為新的V+1xV+1

            在鄰接矩陣中添加頂點的復雜度是O(|V|2)

            Tocy
            Tocy
            翻譯于 09/03 16:18
            0

            那么如何獲得相鄰的頂點呢?

            既然鄰接矩陣擁有一個VxV的矩陣,為了獲得與給定頂點相鄰的所有節點,我們必須進入頂點所在的行,然后獲取它與其他頂點相連的所有邊。

            在之前的示例中,假設我們需要獲得所有與b相鄰的頂點。我們需要獲取存儲b與其他所有頂點連接信息的行數據。


            我們需要遍歷所有節點,

            在鄰接矩陣中獲取相鄰節點的時間復雜度是O(|V|)

            假設你需要將Facebook網絡用圖來表示。你可能需要創建一個20億x20億的矩陣,其中多數節點是空的!沒有人可以認識其他所有人,通常至多幾千人而已。

            通常,我們需要處理稀疏圖的矩陣,因為這種矩陣將浪費大量存儲空間。這就是為什么在多數實現中我們使用鄰接表而不選擇鄰接矩陣的原因了。

            Tocy
            Tocy
            翻譯于 08/31 10:18
            1

            鄰接表

            一種表示圖的比較通用的方法是使用鄰接表. 每一個節點都包含一個列表, 這個列表中的每一個元素都是與該節點相連的.

            可以使用Array(或HashMap)作為鄰接表容器來表示圖, 容器中的元素就是圖節點. 而每一個節點實體又包含一個列表(數組,鏈表,集合等), 來包含與該節點鄰接的節點.

            例如,在上面的圖中, a 與 b 相連接, 同時 a 又連接到自身. 接下來 b 與 c 相連接, 如此繼續下去.

            給定鄰接表中兩個節點是否相連的復雜度是O(n), 其中 n 代表頂點的數量. 也可以寫為O(|V|). 你可以想象, 如果你想知道一個節點與另一個節點是否相連, 你必須遍歷這個列表.

            那么空間復雜度又如何呢?

            將圖存儲為鄰接表的空間復雜度是O(n), 其中 n 是頂點數與邊數的和. 也可以表示為O(|V| + |E|).

            xiaoaiwhc1
            xiaoaiwhc1
            翻譯于 08/31 22:27
            1

            使用鄰接表作為圖表示方式的HashMap實現

            鄰接表是圖的最通用的一種表示方式, 也有很多方式可以實現鄰接表.

            其中最簡單的一種實現方式就是HashMap. 節點值可以作為key, value值是一個鄰接數組.

            增加/移除圖中的頂點經常需要以下操作:

            • 增加/移除邊

            增加/移除頂點也需要更新鄰接表.

            假設我們想移除頂點b, 我們可以這樣做: delete graph['b'];, 可是我們還必須移除鄰接表中頂點d和頂點a對b的引用.

            每次我們移除一個節點, 我們都必須迭代所有的節點列表, 復雜度是 O(|V| + |E|). 有沒有更好的方法呢? 我們后面再回答這個問題. 首先讓我們一起來以一種更"面向對象"的方式來實現我們的表, 這樣做swap操作就會更容易些.

            xiaoaiwhc1
            xiaoaiwhc1
            翻譯于 08/31 23:04
            0

            鄰接表圖"面向對象"實現

            我們先新建一個 Node 類, 頂點值和對應的鄰接頂點作為類成員. 然后創建一個幫助函數來對表進行添加/移除鄰接頂點的操作.

            然后我們讓它變得更快更正確更好. 這里你可以看到: 增加 adjacent 時間復雜度是O(1), 移除 adjacent 的時間復雜度是 O(|E|). 那么如果使用HashSet來代替數組呢? 那將是 O(1). 但是我們先讓它可以運行, 后面再做優化.

            好了, 現在我們有了 Node 類, 接下來讓我們構建 Graph 類, 以及可以實現添加/移除頂點和邊的操作.

            Graph.constructor

            我們需要知道的第一件事是這個圖是個有向圖還是無向圖. 在添加邊時這兩種類型的圖會有所不同.

            xiaoaiwhc1
            xiaoaiwhc1
            翻譯于 08/31 23:18
            0

            圖 --- 添加邊操作(Graph.addEdge)

            增加一條邊需要兩個節點。一個是源節點,一個是目的節點。

            我們增加一條從源頂點到目的頂點的邊。 如果是一個無向圖, 那么我們還要增加一條從目標點到源節點的邊,因為它是雙向的。

            為一個圖的鄰接表增加一條邊的時間復雜度是O(1)

            如果我們要增加邊時,對應的節點不存在,我們就需要先創建它們。接下來我們看如何實現:

            圖 --- 添加頂點操作(Graph.addVertex)

            創建節點的方法就是將它添加到 this.nodes Map中。Map存儲一個鍵值對,key 是頂點值,value 是Node類的實例。下面讓我們看一下代碼:

            如果節點已經存在,我們不需要覆蓋它的值,所以我們首先要檢查節點是否存在,如果不存在,就創建。

            對圖的鄰接表添加頂點的時間復雜度是 O(1)。

            xiaoaiwhc1
            xiaoaiwhc1
            翻譯于 09/02 22:09
            0
            本文中的所有譯文僅用于學習和交流目的,轉載請務必注明文章譯者、出處、和本文鏈接。
            我們的翻譯工作遵照 CC 協議,如果我們的工作有侵犯到您的權益,請及時聯系我們。
            加載中

            評論(0)

            返回頂部
            頂部
            广东快乐十分实时开奖

                  <output id="ilehw"><bdo id="ilehw"><nobr id="ilehw"></nobr></bdo></output>
                  <dl id="ilehw"><font id="ilehw"></font></dl>

                            <output id="ilehw"><bdo id="ilehw"><nobr id="ilehw"></nobr></bdo></output>
                            <dl id="ilehw"><font id="ilehw"></font></dl>