跳至內容

圖形 (資料結構)

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書
一個有3個節點和3條有向圖形

電腦科學中,圖形(英語:graph)是一種抽象資料類型,用於實現數學圖形論無向圖形有向圖形的概念。

圖形的資料結構包含一個有限(可能是可變的)的集合作為節點集合,以及一個無序對(對應無向圖形)或有序對(對應有向圖形)的集合作為(有向圖形中也稱作)的集合。節點可以是圖形結構的一部分,也可以是用整數下標或參照表示的外部實體。

圖形的資料結構還可能包含和每條邊相關聯的數值(edge value),例如一個標號或一個數值(即權重,weight;表示花費、容量、長度等)。

操作

圖形資料結構G支援的基本操作通常包括:[1]

  • adjacent(G, x, y):檢視是否存在從節點xy的邊;
  • neighbors(G, x):列出所有從x出發的邊的另一個頂點y
  • add_vertex(G, x):如果不存在,將節點x添加進圖形;
  • remove_vertex(G, x):如果存在,從圖形中移除節點x
  • add_edge(G, x, y):如果不存在,添加一條從節點xy的邊;
  • remove_edge(G, x, y):如果存在,從圖形中移除從節點xy的邊;
  • 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]
一個二維矩陣,其中行與列分別表示邊的起點和終點。頂點上的值儲存在外部。矩陣中可以儲存邊的值。
關聯矩陣英語incidence matrix[6]
一個二維矩陣,行表示頂點,列表示邊。矩陣中的數值用於標識頂點和邊的關係(是起點、是終點、不在這條邊上等)。

下表給出了在圖形上進行各種操作的複雜度。其中,用|V|表示節點數量,|E|表示邊的數量。同時假設儲存的資訊是邊上對應的值,如果沒有對應值則儲存∞。

鄰接表 鄰接矩陣 關聯矩陣
空間複雜度 [7]
儲存一張圖形
時間複雜度 [8]
添加節點
添加邊
移除節點
移除邊
檢查節點xy是否鄰接(假設已知兩個節點對應的儲存位置)
註釋 移除節點或邊速度較慢,因為需要找到相連的邊或節點 增減節點速度較慢,因為需要修改矩陣的大小 增減節點或邊速度較慢,因為需要修改矩陣的大小

鄰接表在稀疏圖形英語sparse graph上比較有效率。鄰接矩陣則常在圖形比較稠密的時候使用,判斷標準一般為邊的數量|E |接近於節點的數量的平方|V |2;鄰接矩陣也在尋找兩節點鄰接情況較為頻繁時使用。[9][10]

其它表示和儲存圖形的資料結構還包括鏈式前向星十字鏈結串列鄰接多重表英語adjacency multilist等。

平行計算

圖形問題的平行計算主要存在如下幾種困難:處理大量的資料、求解非常規的問題、資料不分散、資料存取對計算的比例很高等。[11][12]面對這些困難,平行計算中圖形的表示和儲存方式很重要。如果選取了不合適的表示方式,可能帶來不必要的通訊花費,進而影響演算法的可延伸性。在本節中,平行計算的共用分散式英語distributed memory儲存模型都在考慮之列。

共用儲存

共用儲存模型下,圖形的表示和非平行計算中的場景是相同的,[13],因為在此模型下,對圖形表示(如鄰接表)的並列讀取操作效率已經足夠高了。

分散式儲存

分散式儲存英語distributed memory模型下,通常會採用劃分英語graph partition點集個集合的方式,其中是並列處理器的數量。隨後,這些點集劃分及相連的邊按照標號分配給每個並列處理器。每個處理器儲存原圖形的一個子圖形,而那些兩個頂點分屬兩個子圖形的邊則需額外特殊處理。在分散式圖形演算法中,處理這樣的邊往往意味着處理器之間的通訊。[13]

圖形的劃分需要謹慎地在降低通訊複雜度和使劃分均勻之間取捨。[14]但圖形劃分本身就是NP難問題。因此,實踐中會使用啟發式方法。

圖形的壓縮儲存

機器學習社會網絡分析等領域中,有時會處理數萬億條邊的圖形。圖形的壓縮儲存可以減少存取和主記憶體壓力。霍夫曼編碼等一些資料壓縮的常見方法是可行的。同時,鄰接表、鄰接矩陣等也有專門的壓縮儲存方法以提高效率。[15]

參見

參考資料

  1. ^ 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 .
  2. ^ Cormen et al. 2001,第528–529頁.
  3. ^ Goodrich & Tamassia 2015,第361-362頁.
  4. ^ Cormen et al. 2001,第529–530頁.
  5. ^ Goodrich & Tamassia 2015,第363頁.
  6. ^ Cormen et al. 2001,Exercise 22.1-7, p. 531.
  7. ^ Cormen et al. 2001,第589-591頁.
  8. ^ Goodrich & Tamassia 2015,§13.1.3.
  9. ^ 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 .
  10. ^ Goodrich, Michael T.; Tamassia, Roberto, Section 13.1: Graph terminology and representations, Algorithm Design and Applications, Wiley: 355–364, 2015 .
  11. ^ 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 (英語). 
  12. ^ 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. ^ 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) (英語). 
  14. ^ Parallel Processing of Graphs (PDF). [2021-08-14]. (原始內容存檔 (PDF)於2021-08-25). 
  15. ^ Besta, Maciej; Hoefler, Torsten. Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations. 27 April 2019. arXiv:1806.01799可免費查閱. 

外部連結