圖 (數據結構)
在計算機科學中，圖（英語：graph）是一種抽象數據類型，用於實現數學中圖論的無向圖和有向圖的概念。
圖的數據結構包含一個有限（可能是可變的）的集合作為節點集合，以及一個無序對（對應無向圖）或有序對（對應有向圖）的集合作為邊（有向圖中也稱作弧）的集合。節點可以是圖結構的一部分，也可以是用整數下標或引用表示的外部實體。
圖的數據結構還可能包含和每條邊相關聯的數值（edge value），例如一個標號或一個數值（即權重，weight；表示花費、容量、長度等）。
操作 編輯
圖數據結構G支持的基本操作通常包括：[1]
adjacent(G, x, y)：查看是否存在從節點x到y的邊；neighbors(G, x)：列出所有從x出發的邊的另一個頂點y；add_vertex(G, x)：如果不存在，將節點x添加進圖；remove_vertex(G, x)：如果存在，從圖中移除節點x；add_edge(G, x, y)：如果不存在，添加一條從節點x到y的邊；remove_edge(G, x, y)：如果存在，從圖中移除從節點x到y的邊；get_vertex_value(G, x)：返回節點x上的值；set_vertex_value(G, x, v)：將節點x上的值賦為v。
如果該數據結構支持和邊關聯的數值，則通常也支持下列操作[1]：
get_edge_value(G, x, y)：返回邊(x, y)上的值；set_edge_value(G, x, y, v)：將邊(x, y)上的值賦為v。
圖的常見數據結構 編輯
- 鄰接表[2][3]
- 節點存儲為記錄或對象，且為每個節點創建一個列表。這些列表可以按節點存儲其餘的信息；例如，若每條邊也是一個對象，則將邊存儲到邊起點的列表上，並將邊的終點存儲在邊這個的對象本身。
- 鄰接矩陣[4][5]
- 一個二維矩陣，其中行與列分別表示邊的起點和終點。頂點上的值存儲在外部。矩陣中可以存儲邊的值。
- 關聯矩陣[6]
- 一個二維矩陣，行表示頂點，列表示邊。矩陣中的數值用於標識頂點和邊的關係（是起點、是終點、不在這條邊上等）。
下表給出了在圖上進行各種操作的複雜度。其中，用|V|表示節點數量，|E|表示邊的數量。同時假設存儲的信息是邊上對應的值，如果沒有對應值則存儲∞。
| 鄰接表 | 鄰接矩陣 | 關聯矩陣 | |
|---|---|---|---|
| 空間複雜度 [7] | |||
| 存儲一張圖 | |||
| 時間複雜度 [8] | |||
| 添加節點 | |||
| 添加邊 | |||
| 移除節點 | |||
| 移除邊 | |||
| 檢查節點x和y是否鄰接（假設已知兩個節點對應的存儲位置） | |||
| 註釋 | 移除節點或邊速度較慢，因為需要找到相連的邊或節點 | 增減節點速度較慢，因為需要修改矩陣的大小 | 增減節點或邊速度較慢，因為需要修改矩陣的大小 |
鄰接表在稀疏圖上比較有效率。鄰接矩陣則常在圖比較稠密的時候使用，判斷標準一般為邊的數量|E |接近於節點的數量的平方|V |2；鄰接矩陣也在查找兩節點鄰接情況較為頻繁時使用。[9][10]
並行計算 編輯
圖問題的並行計算主要存在如下幾種困難：處理大量的數據、求解非常規的問題、數據不分散、數據存取對計算的比例很高等。[11][12]面對這些困難，並行計算中圖的表示和存儲方式很重要。如果選取了不合適的表示方式，可能帶來不必要的通訊花費，進而影響算法的可擴展性。在本節中，並行計算的共享和分佈式存儲模型都在考慮之列。
共享存儲 編輯
在共享存儲模型下，圖的表示和非並行計算中的場景是相同的，[13]，因為在此模型下，對圖表示（如鄰接表）的並行讀取操作效率已經足夠高了。
分佈式存儲 編輯
在分佈式存儲模型下，通常會採用劃分點集 為 個集合 的方式，其中 是並行處理器的數量。隨後，這些點集劃分及相連的邊按照標號分配給每個並行處理器。每個處理器存儲原圖的一個子圖，而那些兩個頂點分屬兩個子圖的邊則需額外特殊處理。在分佈式圖算法中，處理這樣的邊往往意味着處理器之間的通訊。[13]
圖的劃分需要謹慎地在降低通訊複雜度和使劃分均勻之間取捨。[14]但圖劃分本身就是NP難問題。因此，實踐中會使用啟發式方法。
圖的壓縮存儲 編輯
機器學習、社會網絡分析等領域中，有時會處理數萬億條邊的圖。圖的壓縮存儲可以減少存取和內存壓力。霍夫曼編碼等一些數據壓縮的常見方法是可行的。同時，鄰接表、鄰接矩陣等也有專門的壓縮存儲方法以提高效率。[15]
參見 編輯
參考資料 編輯
- ^ 1.0 1.1 參見Goodrich & Tamassia (2015), Section 13.1.2: Operations on graphs, p. 360。更多細節也可參見Mehlhorn, K.; Näher, S., Chapter 6: Graphs and their data structures, LEDA: A platform for combinatorial and geometric computing, Cambridge University Press: 240–282, 1999.
- ^ Cormen et al. 2001，第528–529頁.
- ^ Goodrich & Tamassia 2015，第361-362頁.
- ^ Cormen et al. 2001，第529–530頁.
- ^ Goodrich & Tamassia 2015，第363頁.
- ^ Cormen et al. 2001，Exercise 22.1-7, p. 531.
- ^ Cormen et al. 2001，第589-591頁.
- ^ Goodrich & Tamassia 2015，§13.1.3.
- ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford, Section 22.1: Representations of graphs, Introduction to Algorithms Second, MIT Press and McGraw-Hill: 527–531, 2001, ISBN 0-262-03293-7.
- ^ Goodrich, Michael T.; Tamassia, Roberto, Section 13.1: Graph terminology and representations, Algorithm Design and Applications, Wiley: 355–364, 2015.
- ^ Bader, David; Meyerhenke, Henning; Sanders, Peter; Wagner, Dorothea. Graph Partitioning and Graph Clustering. Contemporary Mathematics 588. American Mathematical Society. January 2013. ISBN 978-0-8218-9038-7. doi:10.1090/conm/588/11709 （英語）.
- ^ LUMSDAINE, ANDREW; GREGOR, DOUGLAS; HENDRICKSON, BRUCE; BERRY, JONATHAN. Challenges in Parallel Graph Processing. Parallel Processing Letters. March 2007, 17 (1): 5–20. ISSN 0129-6264. doi:10.1142/s0129626407002843.
- ^ 13.0 13.1 Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman. Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox. Springer International Publishing. 2019 [2021-08-14]. ISBN 978-3-030-25208-3. （原始內容存檔於2021-08-17） （英語）.
- ^ Parallel Processing of Graphs (PDF). [2021-08-14]. （原始內容存檔 (PDF)於2021-08-25）.
- ^ Besta, Maciej; Hoefler, Torsten. Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations. 27 April 2019. arXiv:1806.01799
.
外部連結 編輯
- Boost Graph Library （頁面存檔備份，存於互聯網檔案館），一個C++的圖程序庫，例如Boost_C++_Libraries。
- Networkx （頁面存檔備份，存於互聯網檔案館），一個Python圖程序庫。
- GraphBLAS （頁面存檔備份，存於互聯網檔案館），一個圖操作的應用程式接口說明。特別關注了稀疏圖。