Graph

圖形

圖形的定義：
G(V,E)
V：表頂點集合（Vertex）
E：表邊集合（Edge）
圖形的分類：有向圖（每個連結屬於單向性質，有箭號）與無向圖（每個連結屬於雙向性質，無箭號）
完全無向圖最多總邊數為n*(n-1)/2
完全有向圖最多總邊數為n*(n-1)
子圖稱為圖形的一部份
Cycle為一個簡單路徑，且起點與終點相同
Connected Component：圖形中任何一點出發均可以抵達任何一個目的點，EX：TREE
有向圖才有強連結，強連結意味任何一點出發，軍可以到達任一目的地點
About Degree
關於分支度：in-degree, out-degree（無向圖只有Degree）

圖形的表示方式
1. adjacency matrix用陣列表示
節點有幾個便是使用幾維陣列表示。兩軸皆為節點編號，1表示與該節點存在連結，0表示與該節點沒有連接。
故有向圖為不對稱陣列，無向圖為對稱陣列（可以僅存上三角或下三角）。
2. adjacency list 用鏈結表示
無向圖：該節點的所有out-degree表示。例如：1可以連結到節點2和4，則表示為1à2à3（箭號為指標指下下一個串列）
無向圖：表示方法同上，僅表示out-degree。間接連結稱為反相鄰矩陣。

圖形追蹤
目的：拜訪所有的節點一次。
方法：
下面兩種搜尋法皆存在多重解，不會是唯一解！
Depth First Search（DFS）
深度搜尋法
Breadth First Search（BFS）
廣度搜尋法

DFS：是以某一個節點為出發點，不斷前進拜訪重未拜訪過的節點，直到無路可走，或是所有相鄰節點皆已經被拜訪，則重回上一個節點，尋找尚未被拜訪過的節點，直到所有相鄰節點均被拜訪。
實做：使用Stack來實做

BFS：是以某一個節點為出發點，以該節點相連接的節點先行拜訪，未連接的節點則不拜訪。出發點與拜訪過的節點形成子圖，與子圖所相鄰的所有節點再先行拜訪，直到所有節點均正確無誤被拜訪完。
實做：利用Queue來實做。

Spanning Tree
擴張樹、展開樹
定義：該圖必為Connected，且任一節點與頂點路徑必為單一路徑。
特色：若非Connected則無Spanning Tree。Spanning Tree存在多重解。N個節點圖形，連接邊數必為n-1個邊。
實做：DFS Spanning Tree、BFS Spanning Tree。

Minimum cost spanning tree
最小成本擴張樹
定義：在圖形符合Spanning的條件下，圖形邊上附有權值，權值加總連接情況為該圖的最小值稱為最小成本擴張樹。
應用：城市交通連接、電路牽線。
運作方法：
1. Kruskal’s algo（克魯斯克爾演算法）
2. Prime’s algo
3. Sollin’s algo
前面兩個比較重要。

Kruskal’s algo
克魯斯克爾演算法
以加入邊觀念為出發點。
Step 1.將圖形（子圖以外）邊權重由小到大排列。
Step 2.從最小權重的邊開始選擇，形成子圖，已形成子圖的節點連接邊不再選擇。
Step 3.重複執行步驟1-2，直到圖形所有節點均被順利連接（均挑選進子圖）。

Prime’s algo
以加入頂點觀念為出發點。
Step 1.從圖形中挑選任一個出發點進入子圖，計算與該出發點相鄰節點的邊權重。
Step 2.挑選與該子圖所有相鄰的權重邊挑選最小權重連接的節點加入子圖。
Step 3.不斷重複步驟2-3，直到所有節點均順利被連接（均挑選進入子圖）。

請注意！最小擴張樹存再唯一解，不論使用哪一種演算法，均可得到相同答案。
意指：可以使用不同演算法來驗算最小擴張樹的正確與否。

Greedy Algorithm
貪婪演算法的定義：
解決最佳化問題的演算法，其解題過程可以看成是由一連串的決策步驟所組成，每一個步驟都有一組選擇要選定。
Greedy Method在每一步驟執行時，總是選定那看起來到目前為止最好的選擇。
但Greedy Method無法保證到最後的結果是最佳解，唯有在某些時候，可以碰巧得到該問題的最佳解答。Greedy是非常有效率及簡單的演算法，但是很難證明其正確性。

圖形的最短路徑
求單一節點到其他節點的最短路徑：O(n^2)
求所有頂點到其他頂點的最短路徑：O(n^3)
Dijkstra’s Algorithm
為了解決從圖形某一特定點抵達各目的地權重問題而設計。
單一頂點到其他頂點的最短路徑實做：利用陣列儲存。（幾個節點則為幾維乘幾維陣列）請使用表格來表示。
從指定的地點開始計算最短路徑，一一藉由擴張方式把所有節點串接，且更新所有連接節點為最小路徑值，最後一列維度表示的即為答案。

AOV Network
用來表示工作先後順序的圖形，且有多重解存在。有Cycle沒有關係。

Topological Order
沒有Cycle的AOV Network，需確定所有工作都有前導作業，不會形成迴圈情況。