---
# System prepended metadata

title: 圖論
tags: [Coding]

---

---
tags: Coding
---
# 圖論
## [**文章連結**](http://alrightchiu.github.io/SecondRound/graph-introjian-jie.html#course)
**Adjacency Matrix(相鄰矩陣)**：一個二維矩陣，若從vertex(A)到vertex(B)有edge，則矩陣位置[A][B]值為1，反之，則為0。
**Adjacency List(相鄰串列)**：先以一個一維陣列列出所有的vertex，再以Linked list表示所有與vertex相連的vertex。

![](https://github.com/alrightchiu/SecondRound/blob/master/content/Algorithms%20and%20Data%20Structures/Graph%20series/Intro_fig/f_5.png?raw=true =400x)

**cycle(循環)**：若有ㄧ條「simple path」的起點vertex與終點vertex相同，則稱這條path為cycle。
**acyclic graph(無循環圖)**：若graph中不存在cycle，則稱這個graph為acyclic graph

![](https://github.com/alrightchiu/SecondRound/blob/master/content/Algorithms%20and%20Data%20Structures/Graph%20series/Intro_fig/f_8.png?raw=true =400x)

**connected**：若存在從vertex(A)指向vertex(B)、以及從vertex(B)指向vertex(A)的edge(若是在directed graph中，需要兩條edge；若是undirected graph只需要一條edge)

![](https://github.com/alrightchiu/SecondRound/blob/master/content/Algorithms%20and%20Data%20Structures/Graph%20series/Intro_fig/f_10.png?raw=true =400x)

**Undirected Graph connected component**: 無向圖的最大連接圖通常就是自己，除非有地方斷開像是G2。

![](https://github.com/alrightchiu/SecondRound/blob/master/content/Algorithms%20and%20Data%20Structures/Graph%20series/Intro_fig/f_11.png?raw=true =400x)

**directed Graph strong connected component**: 有向圖的只要每個點可以互通，那自己就是最大connected component。子圖只要可以加上任意的點或是邊還有connect，就不算是strong connected component。

![](https://github.com/alrightchiu/SecondRound/blob/master/content/Algorithms%20and%20Data%20Structures/Graph%20series/Intro_fig/f_12.png?raw=true =400x)