---
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。


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


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


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


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