[Data Structure] Graph 圖的建構

圖（Graph）的資料結構跟演算法，在各領域皆常被應用。在大量資料構成的集合內，若資料之間存在數值的依賴關係，就有機會用 Graph 建立模型，並使用相關的演算法來解決問題。

Graph 是由頂點 V（Vertex）和邊（Edge）構成的集合：

Figure 1. Graph 由 Edge 跟 Vertex 組成

Edge 可賦予數值或權重，Edge 若有方向性，稱為有向圖（Directed Graph），否則為無向圖（Undirected Graph）。通常我們用 G = [V, E] 來表示一個 Graph。
以程式語言建立 Graph，通常有 2 種方式：

1. 使用 Adjacency Matrix 來表示節點之間連接的關係。例如 Fig. 1 的圖可宣告名為 a 的 4x4 Adjacency Matrix，其中 a[i][j] 內儲存 Vi 跟 Vj 兩個 Vertex 間的 Edge 資訊。舉例來說，我們可以定義若 Vi 跟 Vj 有相連則 a[i][j] == 1，否則 a[i][j] 為 0。並且，可同時宣告另一靜態陣列 v 來儲存每個 Vertex 的資訊。
2. 採用 Adjacency List 來實作 Graph。對於 Fig. 1 的 Graph 結構而言，可用長度 4 的陣列 a 來儲存 Graph，陣列的每個元素關聯到各自的 Linked List，將每個 Vertex 連到的節點維護在 List 內： 

Figure 2. Adjacency Lists 將節點連接關係維護在 Lists 內

之後的文章裡，我會分享我感興趣的幾個 Graph 演算法，跟相關的實作應用。