圖形 (資料結構)

在電腦科學中，圖形（英語：graph）是一種抽象資料類型，用於實現數學中圖形論的無向圖形和有向圖形的概念。

此條目介紹的是抽象資料類型。關於圖論中的基本研究對象，請見「圖形 (數學)」。關於數學函式的圖，請見「函式圖形形」。關於其他主題，請見「圖形」。

一個有3個節點和3條邊的有向圖形

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

圖形的資料結構還可能包含和每條邊相關聯的數值（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]

一個二維矩陣，其中行與列分別表示邊的起點和終點。頂點上的值儲存在外部。矩陣中可以儲存邊的值。

關聯矩陣（英語：incidence matrix）^[6]

一個二維矩陣，行表示頂點，列表示邊。矩陣中的數值用於標識頂點和邊的關係（是起點、是終點、不在這條邊上等）。

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

	鄰接表	鄰接矩陣	關聯矩陣
空間複雜度 [7]
儲存一張圖形	${\displaystyle O(|V|+|E|)}$	${\displaystyle O(|V|^{2})}$	${\displaystyle O(|V|\cdot |E|)}$
時間複雜度 [8]
添加節點	${\displaystyle O(1)}$	${\displaystyle O(|V|^{2})}$	${\displaystyle O(|V|\cdot |E|)}$
添加邊	${\displaystyle O(1)}$	${\displaystyle O(1)}$	${\displaystyle O(|V|\cdot |E|)}$
移除節點	${\displaystyle O(|E|)}$	${\displaystyle O(|V|^{2})}$	${\displaystyle O(|V|\cdot |E|)}$
移除邊	${\displaystyle O(|V|)}$	${\displaystyle O(1)}$	${\displaystyle O(|V|\cdot |E|)}$
檢查節點x和y是否鄰接（假設已知兩個節點對應的儲存位置）	${\displaystyle O(|V|)}$	${\displaystyle O(1)}$	${\displaystyle O(|E|)}$
注釋	移除節點或邊速度較慢，因為需要找到相連的邊或節點	增減節點速度較慢，因為需要修改矩陣的大小	增減節點或邊速度較慢，因為需要修改矩陣的大小

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

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

平行計算

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

共享儲存

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

分散式儲存

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

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

圖形的壓縮儲存

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

參見

• 圖形遍歷
• 圖形資料庫
• 圖形繪製（英語：Graph drawing）