- 圖（graph）
圖的存儲結構
鄰接矩陣（稀疏性）
鄰接表
十字連結清單
圖的周遊（traversing graph）
深搜(Depth_First_search)
廣搜(Breadth_First_Search)
最小生成樹（Minimum Cost Spanning Tree)
1.Prim算法
2.Kruskal算法
Prim算法是以結點為起點，找該點權值最小的邊
Kruskal算法以邊開始，直接找最小權值的邊
邊集數組按權由小到大
最短路徑（shortest paths）
單源最短路徑（single-source shortest paths) —— Dijkstra算法
所有頂點對之間之間的最短路徑（all-pairs shortest paths）
想知道所有頂點到所有頂點的最短路徑，循環v[0]，O(n3) 同樣O(n3)的算法
Floyd算法
拓撲排序（topological sorting）
有向無環圖（directed acyclic graph）
AOV（Activity On Vertex Network）描述一個過程，頂點表示活動，弧表示先後順序（活動之間制約關系）
拓撲序列（topological order）存在v[i]到v[j]的一條路徑，在序列中v[i]必須在v[j]之前
拓撲排序（topological sorting）根據有向圖建立拓撲序列
結果若全部結點都輸出，說明不存在回路，否則說明存在
采用的資料結構：鄰接表
最小生成樹和最短路徑對邊操作，用鄰接矩陣；拓撲排序對結點操作，用鄰接表
關鍵路徑（Critical Path）
AOE（Activity On Edge Network）描述一個過程，頂點表示事件，弧表示活動，弧上的權值表示活動持續的時間
某頂點代表的事件發生，從該頂點出發的活動才能開始；進入某頂點的活動結束，該頂點代表的事件才能發生