# Data Structure - Graph
###### tags: `Data Structure - Graph`
## 前言
## 一 . Graph 基礎
### (一) . 基本概念
1. 圖的數學定義 ： $G(V,E)$
- 代表意義 ： 一個Graph，有$V$這個集合的邊，和$E$這個集合的點。
- $Vertices$ : 點，代表一個圖中的點組成的集合。非空，必有限。
- $Edge$ : 邊，代表一個圖中的邊組成的集合。非空，必有限。

2. 常用的函式 ： $V(G)$和$E(G)$。
- $V(G)$ : 代表G這個圖的點集合。
- $E(G)$ : 代表G這個圖的邊集合。

3. 分類 ：
- 有向圖 ： 邊有方向的，指可向箭頭的邊前進。
- 無向圖 ： 邊無方向的，可以來回任意前進。

4. 規定 ：
- 不可以有$self loop$。
- 有向圖下，任意兩個點間最多只可以有一條線；無向圖為一條。

### (二) . 基本名詞
1. $Complete\ Graph$ :
- 定義 ： 每一個vertices都可以連到其他任一個vertices。
- 數學關係 ： $G$為$Complete\ Graph$下，$E(G)=n(n-1)/2$
2. $adjacent$ :
- 定義 ： 兩個$Vertices$直接相連。
- 注意 ： 間接相連不算。
3. $Subgraph$ : 若$G_1$為$G_0$的子圖。
- 定義 ： $V(G_1)∈V(G_0)$且$E(G_1)∈E(G_0)$ 。
4. $Path$ :
- 定義 ： 由兩$Vertices$連接的邊的集合。
- 有向圖邊的表示 ： $(V_1, V_2)$。
- 無向圖邊的表示 ： $<V_1, V_2>$，此時為有序對。
5. $Length$ :
- 定義 ： 一個path的edge總和
- 注意 ： 若有權重則加上權重。
7. $Degree$ :
- 定義 ： 一個$Vertices$向插出去的$Edge$數。
- $In-degree$ : 內分支度，一個點向內指向的邊個數。
- $Out-degree$ : 外分支度，一個點向外指向的邊個數。
- 數學關係 ： $V(G)=(\sum degree(V))/2$。
- 一個圖的邊數目為每個點的分支度的總和除以二。
### (三). 基本性質
#### $\ \ \ Class \ 1$ : 路徑相關
1. $Simple \ Path$ :
- 定義 : 一個$Path$的起終點可以同，但一個經過的點不可以。
- 注意 ： 起終點不一定要相同，是『可以』相同。
3. $Cycle$ :
- 定義 ： 一個$Simple \ Path$起終點『必』同。
- 注意 ： 起終點一定要相同，比simple path定義更嚴謹。

#### $\ \ \ Class \ 2$ : 圖相關
1. $Connect$:
- 定義 ： 任意圖中兩個點，必有路徑相連(有$path$，不一定為$Simple\ Path$)。
- 無向圖下 : 任意兩點$V_0\ V_1$，有一個path相連。
- 有向圖下 : 有方向後，可能由0到1的不一定可以1到0，因此有向圖下，要有$V_0$到$V_1$和$V_1$到$V_0$的。
3. $Connected\ Component$ :
- 定義 ： 一個圖下，『點個數最多』且『connected』的『subgraph』。

#### $\ \ \ Class \ 3$ : 有向圖相關
1. $Stronly\ Connect$:
- 定義 ： 任意有向圖中兩個點，必有路徑相連，且有$V_0$到$V_1$和$V_1$到$V_0$的。
- 其實上面那個定義就是『connected』，此為專門用於有向圖的『conected』描述。
3. $Connected\ Component$ :
- 定義 ： 一個有向圖下，『點個數最多』且『stronly connected』的『subgraph』。

## 二 . Graph 表示