# 圖論簡介
Graph Theory，簡單來說就是在解決圖(graph)上的問題。
例如:A點能不能走到B點?最短的路是哪一條?等等的問題
## 名詞介紹
[維基百科](https://zh.wikipedia.org/zh-tw/%E9%87%8D%E8%BE%B9)
### 圖
[維基百科](https://zh.wikipedia.org/zh-tw/%E8%BF%9E%E9%80%9A%E6%80%A7_(%E5%9B%BE%E8%AE%BA))

上圖是一張圖(幹話)，可以看到圖(G)是由節點(V)和邊(E)組成，所以記為$G=(V,E)$

### 有向圖
[維基百科](https://zh.wikipedia.org/zh-tw/%E5%9B%BE_(%E6%95%B0%E5%AD%A6))

如果邊具有方向性，稱為有向邊，如果一張圖中有有向邊，則為有向圖。

### 無向圖
=
[維基百科](https://zh.wikipedia.org/zh-tw/%E5%9B%BE_(%E6%95%B0%E5%AD%A6))

沒有方向性的邊稱為無向邊，而所有邊都是無向邊的圖稱為無向圖。
此外，一條**無向邊可以視為兩條有向邊**，所以能在有向圖上使用的演算法都能在無向圖上使用。

### 帶權圖
[維基百科](https://zh.wikipedia.org/zh-tw/%E5%9B%BE_(%E6%95%B0%E5%AD%A6))

如果邊具有權重，稱為帶權邊，如果一張圖有帶權，則為帶權圖。

### 連通圖
[維基百科](https://zh.wikipedia.org/zh-tw/%E5%9B%BE_(%E6%95%B0%E5%AD%A6))

如果一張圖中所有頂點都連在一起，則稱為連通圖。

### 路徑
[維基百科](https://zh.wikipedia.org/zh-tw/%E5%9B%BE_(%E6%95%B0%E5%AD%A6))

由一系列頂點指向所構成。例如:6 -> 4 -> 5 -> 1為一條6走到1的路徑

### 環
[維基百科](https://zh.wikipedia.org/zh-tw/%E5%9B%BE_(%E6%95%B0%E5%AD%A6))

起點=終點的路徑。例如:4 -> 5 -> 2 -> 3 -> 4為一環

### 重邊
[維基百科](https://zh.wikipedia.org/zh-tw/%E9%87%8D%E8%BE%B9)

連接同一對頂點的邊

### 自環

[維基百科](https://zh.wikipedia.org/wiki/%E8%87%AA%E7%8E%AF)
自己連自己的邊。如圖中的節點1具有自環

### 度
[維基百科](https://zh.wikipedia.org/zh-tw/%E5%9B%BE_(%E6%95%B0%E5%AD%A6))

在無向圖中，度=頂點連接的邊數。如圖中的節點5的度為3

[維基百科](https://zh.wikipedia.org/zh-tw/%E5%9B%BE_(%E6%95%B0%E5%AD%A6))

而在有向圖中分為入度和出度，入度=指入頂點的邊數，出度=指出頂點的邊數。如圖中右上角頂點的入度為2，出度為1

### 樹
[維基百科](https://zh.wikipedia.org/wiki/%E6%A0%91_(%E5%9B%BE%E8%AE%BA))

無環連通圖稱為樹

## 儲存方式
### 鄰接矩陣
用一個二維陣列儲存邊。如果a到b有邊，則把v[a][b]記為1。


[圖源](https://zhyjc6.github.io/posts/2020/03/11/%E5%9B%BE%E7%9A%84%E8%A1%A8%E7%A4%BA-%E5%85%B3%E8%81%94%E7%9F%A9%E9%98%B5-%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5-%E9%82%BB%E6%8E%A5%E9%93%BE%E8%A1%A8.html
)

如果邊上有權重，則把v[a][b]記為權重。另外，在無向圖中，因為a到b有邊就代表b到a有邊，所以可以只記一半，節省空間。

### 鄰接表
用一個二維vector儲存連接的頂點。如果節點1可以連接到節點2,5，則v[1]={2,5}。

[圖源](https://www.cnblogs.com/aimmiao/p/9737661.html)

根據需求，第二維可以使用list,set,vector等等容器，只要能儲存所有連到的節點就好了。如果邊上有權重，則可以用pair的形式儲存連到的節點。first儲存節點邊號，second儲存權重。