資料結構與算法整理8——圖
目錄
資料結構與算法整理8——圖
1、圖的相關概念
1.1圖的概念
1.2鄰接矩陣
1.3 空間複雜度
2、圖的周遊/周遊
2.1深度優先周遊
2.2廣度優先周遊
2.3兩種周遊算法的差別
3、最小生成樹算法
3.1PRIM算法
3.2 KRUSKAL算法
4、最短路徑算法：Dijkstra算法
5、拓撲排序、關鍵路徑 AOV AOE
1、圖的相關概念
1.1圖的概念
圖的概念：由頂點集合及頂點間的關系集合組成的一種資料結構。圖是一種非線性結構，圖形結構是資料的邏輯結構的一種，節點使一對多的關系，不具有明顯的分層關系。
| 圖的基本術語 | 解釋及注意事項 |
| 無向圖 | 若 n 個頂點的無向圖有 n(n-1)/2 條邊, 稱為無向完全圖 |
| 有向圖 | 若 n 個頂點的有向圖有 n(n-1) 條邊, 稱為有向完全圖 |
| 無向完全圖 | 在無向圖中任意兩個頂點之間都有連線 |
| 有向完全圖 | 在有向圖中任意兩個頂點之間都有連線 |
| 度 | 頂點的度=出度+入度 |
| 出度 | 頂點指出去的邊 |
| 入度 | 指向頂點的邊 |
| 權值 | 權值可以表示從前一個工程到後一個工程所需的時間或者代價 |
| 路徑長度 | 路徑（path）上邊或者弧的數目 |
| 簡單路徑 | 若一條路徑上頂點不重複出現就稱為簡單路徑 |
| 簡單回路 | 除第一個和最後一個頂點相同外，其餘點不重複的回路稱簡單回路 |
| 回路 | 第一個頂點和最後一個頂點相同的回路或環 |
| 連通圖 | 無向圖中任意兩頂點之間有是連通的，沒有孤立點稱為連通圖 |
| 連通分量 | 無向圖的最大連通子圖稱為連通分量 |
| 強連通圖 | 有向圖中任意兩頂點之間是連通的稱為連通圖 |
| 強連通分量 | 有向圖的最大連通子圖稱為連通分量 |
| 極小連通子圖 | 是指在包含所有頂點并且保證連通的前提下包含原圖中最少的邊。 |
| 生成樹 | 包含圖的全部頂點的一個極小連通子圖 |
1.2鄰接矩陣
（1）順序存儲
鄰接矩陣：用兩個數組表示圖，一個是存儲圖中頂點資訊的一維數組，一個是存儲邊資訊的二維數組。
無向圖：
有向圖：
鄰接矩陣的特點：
- 無向圖的鄰接矩陣是一個對稱矩陣。存放時隻需要存放上三角矩陣的元素即可
- 查找圖中任一頂點的度友善，易于判定任意兩個頂點之間是否有邊相連。對于無向圖而言，頂點vi的度就是鄰接矩陣中第i行或第i列中非o或非∞的元素個數。對于有向圖而言，頂點vi的入度是鄰接矩陣中第i列中非0或非∞的元素個數，頂點vi的出度是鄰接矩陣中第i行中非0或非∞的元素個數。
- 查找圖中任一條邊或弧的權值友善。
（2）序存儲和鍊式存儲的結合
用一個一維頂點數組存儲頂點資訊，每個頂點元素有data域和指針域，指針域存放該頂點的鄰接表的第一個節點的位址。
1.3 空間複雜度
a、當用二維數組表示鄰接矩陣作圖的存儲結構時，查找每個頂點的鄰接點所需時間為O(n^2),其中n為頂點數。
b、當以鄰接表作圖的存儲結構時，找鄰接點所需時間為O(e),其中e為無向圖中邊的數或有向圖中弧的數。
c、當以鄰接表作為存儲結構時，深度優先周遊圖的時間複雜度為O(n + e)。
2、圖的周遊/周遊
周遊：從圖的某個頂點出發，按照一定的順序通路圖中的每個頂點，且每個頂點有且僅有一個被通路。（注意其存儲結構）
2.1深度優先周遊
深度優先周遊：類似與樹的先序周遊，周遊的結果不唯一。通常采用棧實作
解釋：從圖中某個頂點v出發，通路此頂點，然後依次從v的未被通路的鄰接頂點出發深度優先周遊圖，直至圖中所有和v有路徑相通的頂點都被周遊過。若此時圖中尚有未被通路的頂點，則另選圖中一個未被通路的頂點作為起始點，重複上述過程，直到圖中所有頂點都被通路到為止。
2.2廣度優先周遊
廣度優先周遊：類似于樹的層次周遊，采用隊列實作。
解釋：在通路了起始點v之後，依次通路 v的鄰接點；然後再依次（順序）通路這些點（下一層）中未被通路過的鄰接點；直到所有頂點都被通路過為止。
2.3兩種周遊算法的差別
對于上圖的周遊中，深度優先周遊得到的結果是：v0,v1,v3,v7,v4,v2,v5,v6；
廣度優先周遊得到的結果是: v0,v1,v2,v3,v4,v5,v6,v7；
3、最小生成樹算法
最小生成樹：連通圖的生成樹中權值總和最小的生成樹，稱為最小代價生成樹(MST)特點：必須包含所有(n)個頂點；最小生成樹有且僅有n-1條邊；不存在回路。
構造方法：prim算法和kruskal算法。
3.1PRIM算法
假設圖 G=(V,E) 中已落在生成樹上的頂點集為U，則尚未落在生成樹上的頂點集為 V-U，從 (V-U) 頂點集中選取頂點w加U集合，頂點 w 需滿足下列條件：它和生成樹上的頂點之間的邊上的權值是在聯接這兩類頂點的所有邊中權值最小。
3.2 KRUSKAL算法
為使生成樹上總的權值之和達到最小，則應使每一條邊上的權值盡可能地小，自然應從權值最小的邊選起，直至選出 n-1 條互不構成回路的權值最小邊為止。
4、最短路徑算法：Dijkstra算法
最短路徑的概念：即弧的權值之和取最小值的那條路徑
算法思想：按各條最短路徑長度遞增的次序，産生最短路徑的算法。
5、拓撲排序、關鍵路徑 AOV AOE
5.1 AOV網：當有一些活動必須在其他活動完成之後才能開始，用頂點表示活動，弧表示活動間的優先關系，這樣的有向圖稱為AOV網。
5.2 AOE網：用頂點表示事件，弧表示活動，弧上的權值表示活動所需時間構造的有向無環圖稱為AOE網。
5.3拓撲排序算法的步驟：
a、在有向圖中選擇一個入度為0的頂點，輸出該頂點
b、從圖中删除所有以它為尾的弧
c、重複執行a,b，直到找不到入度為0的頂點，拓撲排序完成。
注：若最終圖中仍有頂點存在，不存在入度為0的點，則證明有環若拓撲排序成功則證明無環路。
5.4關鍵路徑
關鍵路徑：AOE網中存在唯一的、入度為零的頂點，叫做源點，存在唯一的、出度為零的頂點，叫做彙點。從源點到彙點的最長路徑的長度即為完成整個工程任務所需的時間，該路徑叫關鍵路徑。