資料結構應試要點——圖

圖的基礎知識請參閱相關書籍，這裡列出考試時需要注意或容易忽視的地方。如有補充，歡迎評論或私信！

圖的基本概念

1.圖可以沒有邊，但不可以沒有頂點。

2.有向完全圖的任意兩相鄰頂點均有一對方向相反的邊。

3.一個圖G的子圖G'并非需要連通，生成子圖包含原圖的全部頂點。

4.極大連通子圖與極小連通子圖：

• 極大連通子圖是無向圖的連通分量，該子圖包含圖中所有的邊。
• 極小連通子圖是既要保持圖連通，包含全部頂點，同時該子圖的邊數最少的子圖。

5.連通圖的生成樹是包含圖中全部頂點的一個極小連通子圖。是以，非全部頂點的子圖一定不是生成樹。

6.有向圖某頂點v的度等于該頂點的入度與出度之和。

7.若從無向圖的任意一個頂點出發進行DFS均可通路所有頂點，則該圖一定是連通圖。

8.存在回路的有向圖必不存在拓撲序列。

9.從某圖G任取一些頂點構成頂點集V'，取一些邊構成邊集E'，由V'和E'構成的圖不一定是G'的子圖，因為E'中邊的兩個結點不一定在V'這個頂點集中。

10.對于一個有n個頂點的圖G：

• 若是連通無向圖，則邊數最少的情況是G是一棵樹。
• 若是強連通有向圖，則邊數最少的情況是G構成一個有向環。

11.對于一個有n個頂點的圖G：

• 若要保證圖G在任何情況下均為連通圖，則需要的邊數至少為（含n-1個頂點的完全圖的邊數）+ 1，這保證了無論這些邊如何配置設定，都能使得它們關聯圖中所有頂點（由反證易得）

圖的存儲及操作

1.鄰接矩陣和鄰接表對頂點的操作很友善。其中，鄰接矩陣适用于稠密圖；鄰接表适用于稀疏圖。

2.十字連結清單和鄰接多重表對邊的操作很友善。其中，十字連結清單适用于有向圖；鄰接多重表适用于無向圖。

3.若鄰接矩陣是三角陣，則圖中必不存在環，即該圖必存在拓撲序列。

4.對于有向圖的鄰接矩陣，第i行（列）非零元素的個數是第i個頂點的出度（入度）。

5.一個圖的鄰接矩陣表示唯一，鄰接表表示不唯一。

• 使用鄰接矩陣生成的廣度優先生成樹或森林與深度優先生成樹或森林唯一，而使用鄰接表則不唯一。
• 基于鄰接矩陣的周遊所得到的DFS序列和BFS序列唯一，而基于鄰接表的周遊所得到的DFS序列和BFS序列則不唯一。

6.畫鄰接矩陣時，若為無權圖則用1表示兩頂點關聯，其餘為0；若為帶權圖，則用數字表示權值，∞表示非關聯，0表示到自身的權值。

7.畫鄰接表時，至少作出兩個域——頂點辨別與指向其關聯頂點的指針，若為帶權圖，則應該增加資料域存儲權值。 

圖的周遊與應用

1.不同方式存儲的圖的DFS與BFS的時間複雜度與空間複雜度：

時間複雜度

鄰接矩陣	鄰接表
DFS	O(|V|²)	O(|V|+|E|)
BFS	O(|V|²)	O(|V|+|E|)

無論是鄰接表還是鄰接矩陣，DFS和BFS的空間複雜度均為O(|V|).

2.利用DFS和求最短路徑算法可以判斷有向圖中是否存在回路。

3.有向無環圖的拓撲序列唯一，不可以唯一确定該圖。

3.最小生成樹不是唯一的，但最小生成樹各邊的權值之和總是唯一的。

4.無向連通圖的最小生成樹必存在。

5.最小生成樹唯一時（各邊權值不同），Prim算法與Kruskal算法得到的最小生成樹相同。

5.最小生成樹的兩個算法：

• Prim算法：時間複雜度為O(|V|²)，是從某一頂點開始，通過選取剩餘頂點中距已選頂點最近的那個頂點構造最小生成樹。由于該算法不依賴邊，因而适用于邊稠密圖。
• Kruskal算法：若采用堆的方式存儲，則時間複雜度為O(|E|log|E|)，是從最小邊開始，通過選取權值最小、兩端頂點屬于不同連通分量的邊構造最小生成樹。由于該算法不依賴頂點，因而适用于邊稀疏而頂點較多的圖。

6.最短路徑的兩個算法：

• Dijkstra算法：以頂點為中心，通過選取剩餘頂點中距離源點最近的那個頂點并更新剩餘頂點到源點的最短路徑來尋找最短路徑。
• Floyd算法：在第k輪更新所有頂點對(vi,vj)間的最短路徑，其中最短路徑的值為min{(vi,vj)的權值 , (vi,vk)與(vk,vj)的權值之和}
• 兩算法時間複雜度均為O(|V|²)，若是求每對頂點的最短路徑，則為O(|V|³)
• Dijkstra算法不适用于含有負權值邊的圖，Floyd算法允許圖中帶有負權值的邊，但不允許該負權值的邊組成回路。

7.關鍵路徑問題：

• 求取關鍵路徑是以拓撲排序為基礎的。
• 關鍵活動一定在關鍵路徑上。
• 在AOE圖中，關鍵路徑上活動的時間延長多少，整個工程的時間也就随之延長多少。
• 縮短所有關鍵路徑上共有的任意一個關鍵活動的持續時間可以縮短關鍵路徑的長度。若某活動并不是該圖中所有關鍵路徑共有的，則它持續時間的縮短并不能縮短整個關鍵活動的持續時間；若活動a與活動b不是所有關鍵路徑共有的，但它們覆寫了所有關鍵路徑（即每一個關鍵路徑必含活動a或活動b），則它們持續時間同時縮短就可以縮短整個關鍵活動的持續時間。
• 關鍵路徑是一個頂點序列，而非活動（邊）序列。
• 将實際工程問題抽象為關鍵路徑問題時，實際問題中的工程與時間分别為關鍵路徑中的活動（邊）與權值，頂點需自行添加。