---
# System prepended metadata

title: Data Structure - Graph
tags: [Data Structure - Graph]

---

# 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 表示