大家好。
在這篇文章中，我決定列出電腦科學中用於儲存圖形的主要資料結構，我還將討論更多這樣的結構，它們以某種方式為我「結晶」。
那麼，讓我們開始吧。 但不是從一開始——我想我們都已經知道圖是什麼以及它們是什麼（有向、無向、加權、未加權、有或沒有多個邊和循環）。
那麼，我們走吧。 我們對於「圖存儲」的資料結構有哪些選擇？
1. 矩陣資料結構
1.1 鄰接矩陣。 鄰接矩陣是行列標題對應圖的頂點數的矩陣，其每個元素a(i,j)的值由頂點之間有無邊決定i 和j（很明顯，對於無向圖，這樣的矩陣將是對稱的，或者我們可以同意我們僅儲存主對角線上方的所有值）。 對於未加權圖，a(i,j)可以透過i到j的邊數來設定（如果沒有這樣的邊，則a(i,j)= 0），對於加權圖，也可以透過權重來設定上述邊緣的（總重量）。
1.2 關聯矩陣。 在這種情況下，我們的圖也儲存在一個表中，通常，行號對應於其頂點的編號，列號對應於預先編號的邊。 如果頂點和邊相互關聯，則在對應的儲存格中寫入非零值（對於無向圖，如果頂點和邊關聯則寫入 1，對於有向圖 - 如果邊關聯則寫入「1」）從頂點“退出”，如果“包含”在其中，則為“-1”（這很容易記住，因為“減號”似乎也“包含”在數字“-1”中））。 對於加權圖，您可以指定邊的總權重，而不是 1 和 -1。
2. 枚舉資料結構
2.1 鄰接表。 嗯，這裡一切似乎都很簡單。 一般來說，圖的每個頂點都可以與任何枚舉結構（列表、向量、陣列…）相關聯，該結構將儲存與給定頂點相鄰的所有頂點的編號。 對於有向圖，我們將只將那些與特徵頂點有「有向」邊的頂點加入這樣的清單。 對於加權圖，實作會更加複雜。
2.2 肋骨清單。 相當流行的資料結構。 正如 Captain Obviousness 告訴我們的，邊列表實際上是圖的邊列表，每條邊都由起始頂點、結束頂點指定（對於無向圖，這裡的順序並不重要，儘管為了統一，您可以使用各種規則，例如，依遞增順序指定頂點）和權重（僅適用於加權圖）。
您可以更詳細地查看上面列出的矩陣列表（並帶有插圖），例如， .
2.3 鄰接數組。 不是最常見的結構。 從本質上講，它是將鄰接表「打包」到一個枚舉結構（陣列、向量）中的一種形式。 此數組的前 n 個（根據圖的頂點數）元素包含同一數組的起始索引，從該索引開始，將與給定數組相鄰的所有頂點寫入一行。
在這裡我找到了最容易理解的（對我自己來說）解釋：
3. 鄰接向量和關聯鄰接數組
事實證明，這些行的作者不是專業程式設計師，而是定期處理圖形，最常處理邊列表。 事實上，如果圖有多個環和邊，那就很方便了。 因此，在開發經典的邊列表時，我建議注意它們的“開發/分支/修改/變異”，即：鄰接向量和關聯鄰接數組。
3.1 鄰接向量
情況 (a1)：未加權圖
我們將未加權圖的鄰接向量稱為偶數個整數的有序集合（a[2i], a[2i+1],...，其中 i 編號為 c 0），其中每對數字是a[2i ]，a[2i+1]分別指定頂點a[2i]與a[2i+1]之間的圖邊。
此記錄格式不包含有關圖是否有向的資訊（兩個選項都可以）。 當使用有向圖格式時，邊被認為是從 a[2i] 指向 a[2i+1]。 這裡和下面：對於無向圖，如果需要，可以應用記錄頂點順序的要求（例如，分配給它的數字值較小的頂點在前）。
在 C++ 中，建議使用 std::vector 指定鄰接向量，因此得名該資料結構。
情況（a2）：未加權圖，邊權重為整數
與情況 (a1) 類比，我們將具有整數邊權重的加權圖的鄰接向量稱為數字 (a[3i], a[3i+1], a[3i+2], ...，其中i 編號為c 0)，其中數字a[3i]、a[3i+1]、a[3i+2] 的每個「三元組」指定編號為a[3i] 的頂點之間的圖的一條邊和a [3i+1]，a[3i+2]的值是這條邊的權重。 這樣的圖也可以是有向的，也可以是無向的。
情況 (b)：未加權圖，非整數邊權重
由於不可能將異質元素儲存在一個陣列（向量）中，因此例如可以採用以下實作。 圖儲存在一對向量中，其中第一個向量是圖的鄰接向量，沒有指定權重，第二個向量包含對應的權重（C++ 的可能實作：std::pair ）。 因此，對於由第一向量的索引 2i、2i+1 下的一對頂點定義的邊，權重將等於第二向量的索引 i 下的元素。
那麼，為什麼這是必要的呢？
好吧，這些行的作者發現它對於解決許多問題非常有用。 那麼，從形式上來看，會有以下幾個優點：
- 與任何其他「枚舉」結構一樣，鄰接向量非常緊湊，比鄰接矩陣（對於稀疏圖）佔用更少的內存，並且相對容易實現。
- 圖的頂點原則上也可以用負數來標示。 如果需要這樣的「變態」怎麼辦？
- 圖可以包含多個邊和多個循環，具有不同的權重（正、負、甚至零）。 這裡沒有任何限制。
- 您也可以為邊指定不同的屬性 - 但有關更多信息，請參閱第 4 節。
但必須承認，這份「清單」並不意味著快速進入邊緣。 在這裡，關聯鄰接數組可以發揮作用，這將在下面討論。
3.2 關聯鄰接數組
因此，如果存取特定邊、其權重和其他屬性對我們來說至關重要，且記憶體需求不允許我們使用鄰接矩陣，那麼讓我們考慮如何更改鄰接向量來解決這個問題。 因此，關鍵是圖的一條邊，它可以指定為一對有序整數。 這看起來像什麼？ 它不是關聯數組中的鍵嗎？ 如果是這樣，我們為什麼不實施它？ 讓我們有一個關聯數組，其中每個鍵（一對有序的整數）將與一個值（指定邊權重的整數或實數）關聯。 在C++中，建議基於std::map容器（std::map 、 int> 或 std::map 、 double>) 或 std::multimap（如果需要多個邊）。 好吧，我們有一個存儲圖的結構，它比“矩陣”結構佔用更少的內存，可以定義具有多個循環和邊的圖，甚至對頂點數的非負性沒有嚴格的要求（我不知道誰需要這個，但仍然）。
4. 資料結構已滿，但缺少一些東西
確實如此：在解決許多問題時，我們可能需要為圖的邊分配一些特徵，並相應地儲存它們。 如果可以明確地將這些特徵減少為整數，則可以使用鄰接向量和關聯鄰接數組的擴展版本來儲存此類「具有附加特徵的圖」。
因此，讓我們有一個未加權的圖，對於它的每條邊，有必要儲存例如 2 個由整數指定的附加特徵。 在這種情況下，可以將其鄰接向量定義為不是「對」的有序集合，而是整數「四重奏」的有序集合（a[2i]、a[2i+1]、a[2i+2 ]、a [2i+3]…) ，其中 a[2i+2] 和 a[2i+3] 將決定對應邊的特徵。 對於具有整數邊權重的圖，順序通常相似（唯一的區別是屬性將遵循邊的權重，並由元素 a[2i+3] 和 a[2i+4] 指定，並且邊本身將被指定為4 個有序數，而不是5 個）。 對於具有非整數邊權重的圖，可以將特徵寫入其未加權的元件中。
當具有整數邊權重的圖使用關聯鄰接數組時，可以指定一個值，而不是單個數字，而是一個數字數組（向量），該數組（向量）除了指定邊的權重外，還指定所有其他必要的值特徵。 同時，對於非整數權重的情況，一個不便之處是需要指定一個帶有浮點數的符號（是的，這是一個不便之處，但是如果沒有那麼多這樣的符號，並且如果你不這樣做的話）不要把它們設定得太「棘手」雙倍，那麼可能就沒什麼了）。 這意味著在 C++ 中擴展關聯鄰接數組可以定義如下： std::map 、 std::vector> 或 std::map ，std::vector，其中「鍵值向量」中的第一個值將是邊的權重，然後是其特徵的數字名稱。
文學：
關於一般圖和演算法：
1. 托馬斯·H·科門、查爾斯·一世·萊瑟森、羅納德·L·裡維斯特、克利福德·斯坦因。 演算法：構造和分析，第二版：Trans。 源自英語– M.：威廉斯出版社，2 年。
2. 赫拉里·弗蘭克。 圖論。 M.：米爾，1973 年。
作者關於這些相同向量和鄰接關聯數組的報告：
3. 切爾諾霍夫 S.A. 鄰接向量和關聯鄰接數組作為表示和儲存圖的方式/SA Chernouhov。 鄰接向量和鄰接圖作為資料結構來表示圖 // 國際科學與實踐會議文章集「實施創新發展成果的問題及其解決方法」（薩拉托夫，14.09.2019 年 2019 月 65 日）。 – Sterlitamak：AMI，69 年，第 XNUMX 頁XNUMX-XNUMX
有關該主題的有用線上資源：
4.
5.
來源： www.habr.com