圖形（Graph）是由所有頂點的集合 (V) 和所有邊的集合 (E) 所組合而成，通常以 G=(V, E) 來表示。

圖形結構分成以下兩種種類：

1. 無向圖形
   無向圖形的邊可以雙向通行，通常使用沒有箭頭的邊，並以 (V1, V2) 表示頂點V1和頂點V2相臨的關係。如下圖所示：
   

2. 有向圖形：
   有向圖形的邊可以理解為單行道，通常使用沒有箭頭的邊，並以 <V1, V2> 表示頂點V1到頂點V2頂點的關係。如下圖所示：
   

圖形資料表示法

1. 相鄰矩陣法（Adjacency Matrix）

   • 假設圖形有 n 個頂點，可以使用大小為 n×n 的二維陣列儲存圖形。
   • 陣列的列索引值為起點，而行索引值為終點。
   • 當頂點間相連或相通，陣列元素為1，反之，頂點間不相連，陣列完素則為0。

   如圖所示：
   
   
   優點：

   • 圖形加入或刪除邊的操作容易。
   • 陣列中的行和列直接對應頂點，此表示法簡單直觀易於理解。

   缺點：如果圖形的邊不多的話，會造成稀疏矩陣，導致空間浪費。

2. 相鄰串列法（Adjacency List）

   • 假設圖形有 n 個頂點，可以使用 n 個鏈結串列儲存圖形。
   • n 個串列首為圖形的 n 個頂點，而串列中的節點為和首節點相連或相通的頂點，最後會指向null。

   如圖所示：
   
   
   優點：比相鄰矩陣法節省空間。

   缺點：因為串列鏈結圖形加入或刪除邊的操作較為麻煩且費時。

3. 相鄰複合串列法（Adjacency Multilist）

   • 假設圖形有 n 個頂點，先使用一個鏈結串列的節點來儲存所有頂點。
   • 假設圖形有 m 個邊，再使用 m 個節點儲存所有邊，此節點包含：邊的標記、邊的起點、邊的終點以及兩個指標分別指向有使用到起點和終點的其它節點，沒有使用到則指向null。

   如圖所示：
   
   
   優點：

   • 比相鄰矩陣法節省空間。
   • 在無向圖中，同一條邊只需存儲一次。
   • 提供更豐富的邊信息，像是權重。

   缺點：查詢特定邊是否存在可能需要遍歷多個指標鏈接。

4. 索引表格法（Index Table）

   • 假設圖形有 n 個頂點，先使用一個一維陣列依照頂點順序儲存和頂點相連或相通的點。
   • 再使用一個索引表格，來記錄各頂點在一維陣列中第一個與該頂點相連或相通的索引位置。

   如圖所示：
   
   
   優點：比相鄰矩陣法節省空間。

   缺點：不能直觀看出各鄰接頂點的信息，需要進一步查找。

參考資料：

1. 蔡明志 (2017)。《資料結構：使用C語言 (第5版)》。臺北：全華圖書。
2. 吳燦銘、胡昭民 (2018)。《圖解資料結構：使用Java》。新北：博碩文化。