Maximum Bipartite Matching

此為Maximum Flow的一種應用。
一張圖分成左邊和右邊，各自有一些vertex，
左邊的點有一些edge連到右邊的點，
我們想要找到最多可以配對幾組。

The Ford-Fulkerson Method

此方法為解決maximum flow的問題，
在閱讀這篇文章之前，
必須先知道flow network的定義。

Flow Networks

把一張圖想像成一個複雜的水道管線，
有起點（source）與匯流點（sink），
每條水管都有流量上限。
我們想要知道，
從起點開始灌水、並經由一些路徑流到匯流點，
要怎麼走才能送出最大量的水、以及最多可以送出多少水。

Johnson's Algorithm

Johnson演算法與矩陣相乘法、Floyd-Warshall演算法一樣，
是用來計算all-pairs的最短路徑，
而當圖的邊很少、也就是應用在sparse graph時，
Johnson演算法的效率會比其他兩種方法還要好。

Transitive Closure of a Directed Graph

此為類似Floyd-Warshall Algorithm的一種應用，
想要知道在Graph中，從vertex i能不能抵達vertex j。

The Floyd-Warshall Algorithm

Floyd-Warshall演算法是用來計算all-pairs的最短路徑，
考慮的是從vertex i直接到vertex j的距離，
以及vertex i經過一些中介點vertex k到vertex j的距離，
去判斷哪個距離比較短。

All-Pairs Shortest Paths with Matrix Multiplication Method

使用一個矩陣(adjacency matrix)W來表示graph，
接著計算一系列的矩陣L⁽¹⁾、L⁽²⁾、...、L^(n-1)，
其中L⁽¹⁾ = W，L^(n-1)代表最後的計算結果。

Dijkstra's Algorithm

Dijkstra's Algorithm是用來計算single-source最短路徑的演算法，

然而限制為Graph裡edge的weight不能是負值。

Single-Source Shortest Path in Directed Acyclic Graphs

在dag中，儘管edge有負值，
但絕對不會有negative-weight cycle，
所以一定可以找到每個點的最短路徑。

The Bellman-Ford Algorithm

此演算法用來解決single-source最短路徑的問題，
而Graph裡edge的weight可以是負值，
不過此演算法不適用有negative-weight cycle的Graph。

Minimum Spanning Tree 最小生成樹 (Kruskal & Prim)

從一個Graph G(V,E)中，分離出一棵包含圖中所有點的樹，

該樹稱為Spanning Tree (生成樹)：

(1) T⊆E，連接G裡面所有的vertex。

(2) T是tree，所以不會有cycle。(T是E的acyclic subset)

(3) T剛好有n-1條edges。

Topological Sort

Topological Sort為depth-first search的一種應用，
可以排序出做某些事的先後順序。

Depth First Search 深度優先搜尋

與breadth-first search類似，
要找出從source到每個可抵達的vertex的其中一種路徑。
不同的點為：
(1) BFS長出一棵樹，而DFS長出多棵樹（Forest）
(2) 會額外記錄timestamp：
    該node一開開始被找到的時間（變成灰色）、
    以及完成搜尋所有和該node相鄰的vertex的時間（變成黑色）。
(3) DFS並不是計算最短路徑（最少edges數量）。

Breadth First Search 廣度優先搜尋

1. 給一個Graph = G(V,E)，以及source vertex s

2. 找出所有s可抵達的vertex

3. 計算從s到每一個可抵達的vertex的最少edges數量

4. 產生BF Tree，s為root，而其他可抵達的vertex都會慢慢加入tree裡。