數(shù)據(jù)結(jié)構(gòu) 圖 3月11日 – 天氣：晴

晚上無線網(wǎng)絡(luò)突然不能用了，花費好久弄這個，耽誤了一些時間

1. 圖的定義

這里需要注意完全圖的定義，以及完全圖的邊數(shù)

這里需要注意連通圖和連通分量的概念。

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

圖有兩種存儲結(jié)構(gòu)，分別是鄰接矩陣和鄰接表。

對于有向圖來說，鄰接矩陣中每一行1的個數(shù)代表了該節(jié)點的出度。每一列中1的個數(shù)代表了該節(jié)點的入度。

對于無向圖來說，每一行或每一列1的個數(shù)代表了節(jié)點的度。

從圖中可以看出來，鄰接矩陣的存儲方式只和節(jié)點的個數(shù)有關(guān)

鄰接表的存儲方式的特點是，鏈表中的每一個節(jié)點代表圖中的一條邊。鏈表中節(jié)點的個數(shù)等于邊的個數(shù)。

對于無向圖來說，鏈表中的節(jié)點必然是偶數(shù)個。

3. 圖的遍歷方式

這里需要重點記住遍歷不同存儲方式的圖的時間復(fù)雜度

4. 圖的最小生成樹

計算最小生成樹的兩種算法

Prim算法每次選擇一條權(quán)值最小的邊，并選擇出頂點，然后從已經(jīng)生成的部分中選擇一條最小的邊與已經(jīng)生成的部分連接，直到所有的頂點都相連。時間負責(zé)度為n^2

它只和頂點的個數(shù)有關(guān)，因此適用于稠密圖（頂點多，邊少）

Kruskal算法每一次都選擇圖中最小的一條邊，直到所有的頂點都被連接。

它只和邊的個數(shù)有關(guān)，因此適用于稀疏圖。

5. 拓撲排序

每次選擇入度為0的節(jié)點，刪除節(jié)點和與之相連邊，直到不存在入度為0的頂點

注意：拓撲排序的順序不一定唯一

6. 關(guān)鍵路徑

關(guān)鍵路徑可能不唯一

關(guān)于最早最晚開始時間以及松弛時間的計算問題：
https://blog.csdn.net/zhangt2333/article/details/107029298

7. 最短路徑

無需掌握這兩種算法具體怎么計算的，考試的時候直接看圖就可以找到兩個頂點之間的最短路徑