圖 (抽象資料類型)

一幅有向圖，有三粒綟（藍珠）同三條檠（黑箭）

圖係電腦科學裏頭嘅一種抽象數據類型，旨意實現數學嘅圖論領域啲無向圖同有向圖嘅概念喺電腦當中。

圖數據結構包括一個有限嘅（又可能變得嘅）集含有啲「頂點」（亦都喊做「綟」或者「點」），同埋一個集含有啲頂點𠵿，啲𠵿喺無向圖就係無序𠵿、喺有向圖就係有序𠵿。啲𠵿喊做「檠」（亦都喊做「紷」或者「線」）。對於有向圖又喊做「檠」，但有時亦都喊做「箭咀」或者「弧」（arcs）。啲頂點可以係圖結構嘅一部分，又可以係啲外部實體、攞整數嘅索引或者參照表示返嘅。

圖數據結構仲可以捉某啲檠值戥每條檠相關聯，例如符號標籤或者數字屬性（成本、容量、長度等）。

操作

圖數據結構G提供有嘅基本操作通常包括：

• adjacent(G, x, y)：測試從綟x到綟y有檠冇；
• neighbors(G, x)：列嗮啲綟y，係有一條檠從綟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)：get個戥綟x關聯嘅值；
• set_vertex_value(G, x, v)：set個戥綟x關聯嘅值成v。

對於啲結構，啲檠加有值嘅，通常仲提供埋：

• get_edge_value(G, x, y)：get個戥檠(x, y)關聯嘅值；
• set_edge_value(G, x, y, v)：set個戥檠(x, y)關聯嘅值成v。

圖表示嘅常用數據結構

鄰接表

啲綟儲成記錄或者對象，每粒綟儲一版相鄰綟嘅列表。種數據結構允許喺綟度儲埋啲附加數據。若果檠亦都儲成對象，就儲得附加數據，喺種情況下，每粒綟儲住佢條搭配檠，每條檠儲住佢粒搭配綟。

鄰接矩陣

二維矩陣，其中行代表住源綟，列代表住目標綟。檠同綟上高嘅數據必須儲喺外部。只有一條檠嘅成本儲得喺每副綟之間。

關聯矩陣

二維矩陣，行代表住綟，列代表住檠。一欄表示行綟同列檠之間嘅關聯。

下表寫有啲時間複雜度成本畀喺圖上執行各種操作嘅，對於啲表示裏頭嘅每一個，用|V|綟數同|E|檠嘅數量。 喺矩陣表示當中，啲欄編碼有成本畀爬檠。對於嘸存在嘅啲檠，成本着假定為∞。

	鄰接表	鄰接矩陣	關聯矩陣
存圖	$O(|V|+|E|)$	$O(|V|^{2})$	$O(|V|\cdot |E|)$
添綟	$O(1)$	$O(|V|^{2})$	$O(|V|\cdot |E|)$
添檠	$O(1)$	$O(1)$	$O(|V|\cdot |E|)$
剷綟	$O(|E|)$	$O(|V|^{2})$	$O(|V|\cdot |E|)$
剷檠	$O(|V|)$	$O(1)$	$O(|V|\cdot |E|)$
綟x同y係相鄰冇？（假設已知佢哋所儲位置）	$O(|V|)$	$O(1)$	$O(|E|)$
註	剷綟、檠好慢，因為要搵嗮啲綟或者檠	添、剷綟好慢，因為要調整矩陣大細/複製矩陣	添、剷綟、檠都好慢，因為要調整矩陣大細/複製矩陣

鄰接表通常係首選，因為可以有效噉表示得到啲稀疏圖。首選鄰接矩陣嘅情況係，若果幅圖係密集嘅（即檠數|E|接近綟數嘅平方|V|²），或者若果有檠連接兩粒綟嘅必須快速搵得到。

平行表示

圖相關問題嘅平行化有返啲重大挑戰：數據驅動計算、非結構化問題、局部性差，高數據訪問/計算比。圖啲表示使喺平行架構嘅喺應對啲挑戰方面發揮到重要作用。揀啲表示嘸啱可能會增加多餘嘅通訊成本畀個演算法，會降低佢個可擴展性。下便會考慮共享同分佈式嘅內存架構。

共享內存

共享內存模型嘅情況下，攞嚟平行處理嘅圖表示戥順序情況下嘅相同，因為喺共享內存度平行噉只讀訪問個圖表示（例如鄰接表）都仲算高效。

分佈式內存

喺分佈式內存模型裏頭，通常嘅做法係捉幅圖個綟集$V$進行分墢，轉成$p$套$V_{0},\dots ,V_{p-1}$，其中$p$係可用嘅等處理元素（processing elements，PE）數量。然之後，綟集啲墢着分佈到有匹配索引嘅PE，佮埋相應嘅檠。每個PE都有自己嘅子圖表示，其中喺另一墢裏頭有端點嘅檠需要特別注意。對於似MPI（Message Passing Interface）噉嘅標準通訊接口，擁有另一個端點嘅PE，佢個ID必須係識別得到嘅。喺分佈式圖演算法嘅計算過程裏頭，沿住啲檠傳遞訊息即係通訊。

圖分墢（Graph partition）有必要謹慎，低通訊度戥大細分得均勻兩者係需要權衡嘅；圖分墢係一個NP難題，所以計算係嘸行得嘅。相反，以下啲啟發式方法就有使到。

1D分墢：每個處理器都得到$n/p$綟同相應嘅輸出檠。呢個可以理解為鄰接矩陣嘅行或者列分解。對於喺此表示上運行嘅演算法，需要一個All-to-All通訊步驟同埋${\mathcal {O}}(m)$消息緩衝區嘅大細，因為每個PE可能有到每個其他PE嘅傳出檠。

2D分墢：每個處理器獲得鄰接矩陣嘅一個子矩陣。假設處理器喺一個矩形裏頭對齊$p=p_{r}\times p_{c}$，其中$p_{r}$同$p_{c}$分別係每行同每列裏頭處理元素嘅數量。然之後每個處理器得到維數鄰接矩陣嘅一個子矩陣$(n/p_{r})\times (n/p_{c})$。呢層可以可視化成矩陣入面嘅棋盤圖案。所以，每個處理單元只能有出到同行同列啲PE嘅檠。噉每個PE嘅通訊搭檔數量就着限制為$p=p_{r}\times p_{c}$種可能性當中嘅$p_{r}+p_{c}-1$。

壓縮表示

喺機器學習、社交網絡分析同其他領域有啲圖係有數万億條檠嘅。壓縮過嘅圖表示經已有開發出嚟，着攞嚟減少I/O同內存嘅要求。Huffman編碼等通用技術都適用，但可以透過特定方式處理啲鄰接表或者鄰接矩陣嚟提高效率。

睇埋

• 圖遍歷
• 圖數據庫，提高圖（數據結構）嘅持久性
• 圖寫過，基於規則轉換啲圖嘅
• 圖繪製軟件