[Algorithm] Day.9 Graph

終於來到了資料結構的最後一個章節 Graph，也就是圖，但因為圖實在有點過於博大精深，所以今天就先介紹一些專有名詞跟他的表示方式

定義

一個 graph G 裡面會包含兩個集合 V 和 E，其中 V 是一個有限且不為空白的頂點 vertices (也就是 nodes，我們在圖裡面都稱為 vertices) 的集合；而 E 就是成對的 vertices 的集合，我們把這些對子稱為邊 (Edge)；所以我們就會把這張圖 G 寫成 G = (V,E)

而圖依據他有沒有指向性又可以分為 無向圖 (undirect graph) 和 有向圖 (direct graph)，其中在 undirect graph 裡 (u,v) 和 (v,u) 因為沒有方向性所以是相同的，但如果是 direct graph，(u,v) 指的就是從 u 到 v 的邊，而 (v,u) 則相反，因此這兩個是表示不同的邊。

在表示圖的時候，一般講到 graph 都會默認為是 undirect graph，若要表示 direct graph 則會使用 digraph 這個詞

在下圖中我們就可以看到 G1 和 G2 是 undirect graph 而 G3 則是 direct graph

這邊可以發現 G2 其實就是一棵樹，因為樹就是一種圖的特例

限制

對於圖我們會有一些限制：

1. 一個圖不能有邊是連回到自己的（不能 self-loop），如下圖(a)中點 1 中的邊
2. 兩點中間不能有重複的邊，如下圖(b)中點 2,3,4 中間都有重複的邊

而基於以上的限制，我們就可以推算出每張圖邊的最大數量，如果是 undirect graph，因為 (u,v) 等於 (v,u)，所以最多只會有 n(n-1)/2 個邊，而 direct graph 則因為兩點之間可以存在兩條指向不同的邊，所以最多可以有 n(n-1) 條邊。如果一個無向圖有最大數量 n(n-1)/2 條邊，我們就稱它為 complete graph

圖中的專有名詞

1. Path：連接兩個很遠點中間的路徑
   1. Simple Path：Path 中沒有重複經過同一條邊
   2. Cycle：Path 的頭尾是同一個 vertix
   3. Length：一個 path 總共經過多少 vertices
2. Degree：一個 vertix 有多少個邊
   1. in-degree：在 direct graph 中，一個頂點以他為結束點的邊數量
   2. out-degree：在 direct graph 中，一個頂點以他為起始點的邊數量
3. Subgraph：Graph 的某一部分
4. Connected：如果兩個 vertices 中間有一條 path 就代表這兩點是 connected 的
5. Connected Component：也可以直接叫 Component，指的是當今天一個 Graph 的 subgraph 覆蓋到這個 graph 的最大範圍就稱為 Component 像上圖兩個都是有包含到 G4 的最大範圍，所以就可以稱為 G4 的 connected component，但如果今天只有包含 1、2、3 三個點的話就因為沒有包含最多點所以不是 component
6. Strongly Connected：在 digraph 中，如果兩個點中間有互相連通的邊，就稱為 strongly connected，例如在 1、2 中間有 (1,2) 和 (2,1) 兩個邊就稱 1、2 為 strongly connected

圖的表示方式

1. 鄰接矩陣 (Adjacency Matrix)

如果我們有一個由 n 個 vertices 組成的圖，他的鄰接矩陣就會是一個 n 列 * n 行 的矩陣，矩陣中只會有 0 和 1 兩種值。若值為 0 則代表兩點之間沒有邊；1 則代表兩點之間有邊

這個矩陣會因為不能存在 self-loop 的原因所以主對角線上的值都會是 0。如果是無向圖的話會因為邊沒有方向性，所以矩陣一定會是對稱矩陣

最後如果要算每一個 vertix 的 degree，就只需要把他那一行/列的數值相加就可以求得

2. 鄰接串列 (Adjacency List)

這是利用串列的方式把相鄰的 vertices 連起來，在 head node 的 list 中儲存可以和 head node 連接的 vertices，他的優點是可以節省儲存空間

無向圖

如果今天是一個有著 n 個 vertices 和 e 個 edge 的無向圖，那我們可以把它存在一個長度為 n+2e+1 的陣列當中

我們稱這個陣列為 a，在 a 中 index 1 到 9 代表他總共有 9 個 vertices，而 a[1] 為 10，代表我們要從 index 10 開始看 index 1 所連接的 vertices；而 a[2] 為 12，所以代表要從 index 12 開始看 index 2 所連接的點。從上面兩個條件可以看出連接 index 1 的 vertices 就會是 a[10] 和 a[11]，也就是 3 和 2

之後讓我們看到 index 9 的地方，a[9] = 24，但明明只有 a 的長度只有 23，當今天 a[n] > a.size() 的時候，就代表他是圖中最後一個 vertices，從這一格之後開始的值都是指連接的點而不是告訴大家從哪裡開始看

這個 Sequential Representation 的優點就是他的標示非常的簡單好懂，但缺點就是難以擴充

有向圖

有向圖就相對比較麻煩，因為有方向性的問題，所以除了 adjacency list 以外會需要多存一個 inverse adjacency list，目的是為了要計算每個點的 in-degree

上圖中的第一個 list 存的就是 G3 的 out-degree，而下面的 inverse list 存的就是 G3 的 in-degree

除了使用 inverse list 以外，還有另外一個方式是把原本的 adjacency list 進行擴充，變成一個 4 欄的 list，分別為 tail、head、column link for head、column list for tail

3. 鄰接多串列 (Adjacency Multilist)

最後就是 Adjacency Multilist 了！上述兩個表示方式都是針對頂點進行處理，這個方式則是針對邊進行處理

如上圖，我們可以看出 G1 總共有 6 個邊，因此有 N1 到 N6 總共 6 個 list，在這 6 個 list 中個會存五個值，如下

利用這個多串列，我們可以看出從第一個邊是 (1,2)，另一個連接到 1 的邊是 N2，跟另一個連接到 2 的邊是 N4 這三個訊息。所以看到 N2 可以知道還有 (1,3)，之後一樣從後面 N3 的後面兩格看出 1 和 3 還有哪些邊會連接。

之後看到 N3 發現他的第四格 Link to V1 是 0，這就代表已經列完所有和 1 這個 vertix 有關連的邊；以此類推就可以從這個 multilist 中得知整個圖的長相了！