# 圖論基礎觀念
> 上一篇文章　[前綴和](https://hackmd.io/Dev0QF2US2a29hTVH3HdpA)
> 下一篇文章　[生成最小樹](/7isAK0zGTFeWEBy52goe2w)
> 先備知識　　無
> 延伸閱讀　　無
---
## 前言
圖論(Graph Theory)是探討關於「圖(Graph)」這個數學模型的理論。只要能將問題套用到graph上，就有方法可以解決這個問題。
## Graph基本觀念
Graph 是由節點（Vertex，有時也稱 Node）和邊（Edge）構成。
>`Vertex` : 承載資料
>`Edge` : 表達這些資料或對象間的關係
如果將Graph畫出來，vertex通常被畫成一個點，而edge就是線，將一個個節點(vertex)連起來。
例圖如下:
其實看起來有點像心智圖，生活中也有很多類似的例子，像是族譜、人物關係圖或是捷運路線圖等等。

## Graph的種類
### ==帶權圖（Weighted Graph）與無權圖（Unweighted Graph）==
>依照Edge是否帶有額外資訊決定，例如在捷運圖中站點之間所花時間之類的。
>這些額外的因素我們稱為==權重(Weight)==
>可以將Weight寫在Edge上
>如下圖片所示:
>

:::info
Edge 是否有方向性，以及 Edge 是否帶權，是個別獨立的，這些特性可以重複。
:::

### ==無向圖(Undirected Grapg)==
>無向圖的邊(Edge)為無向邊，可以表示為$(u, v)$代表$u$到$v$之間的邊，==可以相互往來==。
如例圖所示:
以下還有一些例子:

| Graph | V(G~i~) | E(G~i~) |
| -------- | -------- | -------- |
| G~1~|{0,1,2,3}| {(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}|

>如果將資訊畫成圖就會像下圖所示:

### ==有向圖(Directed Graph)==
>有向圖的邊(Edge)為有向邊，可以表示為$<u, v>$代表從$u$到$v$的邊，不能相互往來，==只能從$u$到$v$，$v$不能到$u$==。
如例圖所示:
>
>以下還有一些例子:

| Graph | V(G~i~) | E(G~i~) |
| -------- | -------- | -------- |
| G~2~|{0,1,2}| {<0,1>,<1,0>,<1,2>}|

>如果將資訊畫成圖就會像下圖所示:
>

## Graph的儲存方式
既然我們已經知道圖的基本概念了，接下來就要知道圖是如何儲存在程式碼中的。
常見的圖的儲存方式有兩種 `鄰接矩陣` 以及 `鄰接串列` 都是用Python中的List去存資料。

### ==鄰接矩陣 (Adjacency Matrix)==
>使用一個二維陣列存節點之間的關係，有點像表格。
>假設有$N$個節點，那就需要一個$N*N$的矩陣
>矩陣的index代表節點編號，如果今天存在$u$→$v$的邊，則$G$[$u$][$v$] = 1，否則就$G$[$u$][$v$] = 0。
>
>以上面這個無向圖作為範例，我們需要一個$4*4$的矩陣

>**範例程式碼**
> ```python=
> # Python
> # 範例：有 4 個節點的無向圖
> Graph = [
> [0, 1, 1, 0], # node 0 連到 1 跟 2
> [1, 0, 0, 1], # node 1 連到 0 跟 3
> [1, 0, 0, 1], # node 2 連到 0 跟 3
> [0, 1, 1, 0], # node 3 連到 1 跟 2
> ]
> ```
> :::success
> 優點:直覺簡單
> :::
> :::danger
> 缺點:空間浪費
> :::

### ==鄰接串列 (Adjacency List)==
>也是用二維陣列去存節點之間的關係，但與前面不同，一個$N$個節點的圖不需要一個$N*N$的矩陣去存取它。
>Adjacency List中每個index對應一個節點，裡面放它連出去的節點
>
>一樣以上圖為例
>>**範例程式碼**
> ```python=
> # Python
> # 範例：有 4 個節點的無向圖
> Graph = [
> [1, 2], # node 0 連到 1 跟 2
> [0, 3], # node 1 連到 0 跟 3
> [0, 3], # node 2 連到 0 跟 3
> [1, 2], # node 3 連到 1 跟 2
> ]
> ```
> :::success
> 優點:省空間
> :::
>
> :::danger
> 缺點:查有沒有連邊要掃 list
> :::
>
### ==如何存節點上的資料==
>看到這邊，你一定有疑問，上面教的儲存方式好像只能表示節點與節點之間的關係，啊我真正的資料要放哪裡?
>>**很簡單，通常會另外用個陣列或字典來對應節點資料**
>>
>下面用一個例子示範
> :::success
> 假設我們有 3 個節點，代表 3 個人，之間的Edge表示朋友關係：
> 
>```python=
># Python
># 圖的 adjacency list
>graph = [
> [1], # 0 跟 1 連
> [0, 2], # 1 跟 0、2 連
> [1] # 2 跟 1 連
>]
>
># 節點的資料
>node_data = [
> {"name": "阿明", "age": 25},
> {"name": "小美", "age": 23},
> {"name": "大雄", "age": 30}
>]
>
> ```
> :::

---
> 上一篇文章　[前綴和](https://hackmd.io/Dev0QF2US2a29hTVH3HdpA)
> 下一篇文章　[生成最小樹](/7isAK0zGTFeWEBy52goe2w)
> 先備知識　　無
> 延伸閱讀　　無