圖的應用（最小生成樹，拓撲排序）

介紹

應用圖解決現實問題是我們使用圖這種資料結構的原因所在。

最小生成樹是圖的應用中很常見的一個概念，一個圖的最小生成樹不是唯一的，但最小生成樹的邊的權值之和縱使唯一的。最小生成樹的算法主要有Prim算法和Kruskal算法。這兩種算法都是基于貪心算法政策（隻考慮眼前的最佳利益，而不考慮整體的效率）。

拓撲排序是指由一個有向無環圖的頂點組成的序列，此序列滿足以下條件：

1. 每個頂點出現且僅出現一次
2. 若頂點A在序列中排在頂點B之前，則圖中不存在頂點B到頂點A的路徑。

最小生成樹

Prim算法

Prim算法非常類似與尋找圖的最短路徑的Dijkstra算法。

算法思路：

1. 首先将圖的任一節點加如樹中
2. 之後選擇一個與目前頂點最近的節點接入樹中。
3. 循環 2直到所有節點均被接入樹中。

Prim算法的時間複雜度是O(V*V),不依賴于E，是以他适合邊稠密的圖的最小生成樹。

Kruskal算法

克魯斯卡爾算法是一種按權值的遞增次序選擇合适的邊來構造最小生成樹的方法。

算法思路：

1. 初始時隻有n個頂點而無邊的非連通圖，每個頂點自成一個連通分量
2. 按照邊的權值由小到大，不斷選取目前未被選取過且權值最小的邊
3. 若該邊依附的頂點落在圖的不同的連通分量，則将該邊加入樹中，否則舍去，直到所有頂點都在一個連通分量。

Kruskal的時間複雜度為O(Elog2E),是以此算法适合構造邊稀疏而頂點稠密的圖的最小生成樹。

拓撲排序

對一個AOV網進行拓撲排序的算法有很多，下面介紹一種。

1. 從AOV網中選擇一個沒有前驅的節點進行輸出
2. 從網中删除該頂點和所有以它為起點的有向邊
3. 重複1和2，直到目前的AOV網為空，或者目前網中不存在無前驅的頂點為止。後面一種情況說明有向圖中必然存在環。

後續