本文為交通大學開放式課程上課心得整理。
在開始圖論之前，先介紹一下處理演算法問題的幾個要點：
car theorem 認為解決問題有三件事情是最重要的：Criticality、Abstraction、Restriction。
Criticality 指的是在解決問題時，務必先了解問題的本質，找出最核心要處理的項目並去掉枝節；當問題越乾淨的時候，思考也會相對越清晰。
Abstraction 指的是將需要處理的對象／問題，用抽象化的方式表現它。graph 就是 Abstraction 最好的例子。
處理問題時，通常會伴隨一些很瑣碎的相關問題，影響主要問題的解決進度，這時就可以嘗試將這些瑣碎的周邊問題簡化，也就是 Restriction。Restriction 並不是將小問題簡化之後便忽視，而是先著重在處理主要項目，等基本演算法成型之後，再將這些比較次要的事情考慮進去，嘗試在演算法的延伸或是調整演算法一併處理。
基本概念
圖論的起源為普魯士柯尼斯堡的七橋問題（因在資料結構已經紀錄過，此處不再贅述）。Graph 主要是用來記錄 Object 之間的關係，主要有兩個類別：點（node，或 vertex）與線（edge）實務上常用 G = ( V, E ) 來表示；若想要描述兩點 U、V 之間有線 E 相連接，則通常用 E = { U, V } 來表達。
圖還可以再從線的型態做細分，如果線沒有方向性稱為無向圖（Undirected Graph），點與線之間的關聯會以大括號紀錄（如上段最後）；反之如果有方向性，則稱為有向圖（Directed Graph），須改用小括號表達。兩個有線相連的頂點互為彼此的鄰居（neighbor）。
Paths and Connectivity
假設給定一個無相圖 G = ( V, E )，路徑（path）指的就是一串由一個頂點到另一個頂點的序列，常見的表達方法為 P = < V1, V2, V3, … Vk>；如果該路徑所經過的點彼此之間不重複，則我們稱呼這條路徑為簡單路徑（simple path）。
如果路徑的頂點等於終點，這種特殊路徑稱為圓（Cycle）。
如果一個無相圖的狀態為相連（connected，或 reachable），則圖內每兩個點之間皆存在一條路徑；若兩個點之間存在一條以上的路徑，則此兩點之間的距離（distance）為所有路徑中最短的一條（線的數目最小的），反之，若兩點之間沒有任何路徑可以抵達，則稱為 disconnected，距離為無限大。
Trees
資料結構中的樹（Tree）也是圖的一種，一個相連、沒有 Cycle 的無向圖就可以視為一棵樹。樹有一些規則，只要符合其中兩項，就可以推得第三項，介紹如下：
- 頂點之間相連
- 沒有 Cycle
- 擁有 n − 1 條邊
由於樹就是一個簡單的無向圖，因此每個節點之間都只存在一條路徑。
無向圖可以任意選擇某個節點當作 root 來構成 tree，如果有特別指定 root 的圖便稱為 Rooted Tree，由於 Rooted Tree 本身有階層（hierarchy），方便做一些理論上的探討，因此很常被使用（樹的相關資訊在資料結構已經紀錄過，此處只簡單節錄）。
Node-to-Node Connectivity
假設一個圖 G = ( V, E )，裡面有兩個節點 s、t，是否存在路徑連接 s、t？這就是 s-t connectivity problem。
s-t 問題常用於迷宮的探討，而探討路徑的方式：BFS 以及 DFS，已於資料結構相關章節述及，此處不再重複紀錄。
Connected Component
在無向圖中，Connected Component 是一個很重要的概念，用來探討給定一個特殊點時，是否存在路徑從該點到達的其他點。
如何表達一張圖
要表達一張圖，顧名思義，就是要想辦法維護點集合與線集合，常用來表達圖的方法有兩種：
・Adjacency Matrix：如前所述，圖要探討的是點之間的關聯，因此對圖來說最重要的就是線。Adjacency Matrix 顧名思義就是以矩陣的形式表達圖，Adjacency Matrix 在無向圖中是一個對稱形式的矩陣，假設一個集合中有 n 個點，便會造出一個 n x n 的矩陣，用 0 與 1 紀錄兩個點之間的關係。
在 Adjacency Matrix 中，如果想知道兩點之間有沒有線相連，只要直接查詢對應的欄位即可，時間複雜度為 O(1)；若想知道點和多少相異點相鄰，只需要掃相應的欄或列加總即可，時間複雜度為 O(n)。
・Adjacency List：以 Linked List 的形式表達圖。首先先做出陣列儲存圖裡面對應的點，再用 list 紀錄點與點之間的對應關係。
Adjacency List 中要確認兩點之間是否相連，必須從相應的點出發，掃描 List 中是否有該點存在，時間複雜度為 O(n)。
相關連結：
