1. 圖的基本概念

1) 有向完全圖

2) 無向完全圖

3) 路徑長度

4) 簡單路徑

5) 連通圖，連通分量

6) 強連通圖，強連通分量

7) 生成樹，生成森林

2. 圖的存儲結(jié)構(gòu)

1) 鄰接矩陣：可方便計算入度和出度；基于此種結(jié)構(gòu)的圖，遍歷結(jié)果唯一。

2) 鄰接表：適用于點多邊少的情況；基于此種結(jié)構(gòu)的圖，遍歷不唯一（鄰接表不唯一）

3. 圖的遍歷：通過遍歷，可以求得圖的所有連通分量

1) 深度優(yōu)先遍歷：類似于二叉樹的先序遍歷

2) 廣度優(yōu)先遍歷：類似于二叉樹的層次遍歷

4. 最小生成樹

1) 普利姆算法（從某點開始，逐次搜索，添加節(jié)點，）

2) 克魯斯卡爾算法

5. 最短路徑

1) 迪杰斯特拉算法

2) 佛羅里德算法

6. 拓撲排序：圖的拓撲排序可以接觸依賴關(guān)系以及判定圖中是否有環(huán)。

7. 關(guān)鍵路徑：通過AOE，可以求得圖中頂點的最早開始時間，最晚開始時間，活動的最早開始時間，以及活動的最晚開始時間。