主要知識點

• 圖的概述
• 圖的存儲結(jié)構(gòu)
• 圖的遍歷
• 最小生成樹
• 最短路徑
• 拓撲排序
• 關(guān)鍵路徑

一、圖的概念

圖的定義：

• 圖是由頂點集V和頂點間的關(guān)系集合E（邊的集合）組成的一種數(shù)據(jù)結(jié)構(gòu)，可以用二元組定義為：G=（V,E）。

• 圖中的數(shù)據(jù)元素稱為頂點

基本概念

• 無向圖：全部由無向邊構(gòu)成的圖稱為無向圖(Undirected Graph).
• 有向圖： 全部由有向邊構(gòu)成的圖稱為有向圖(Directed Graph).

6.1無向圖和有向圖.png

• 權(quán)： 在圖的邊或弧中給出相關(guān)的數(shù)（非負），稱為權(quán)。
• 網(wǎng)：圖上的邊或弧帶權(quán)則稱為網(wǎng)。

6.2無向網(wǎng)和有向網(wǎng).png

• 無向完全圖(Undirected Complete Graph)：無向圖，邊的取值范圍是0到n(n-1)/2；邊數(shù)達到最大值n(n-1)/2條邊的無向圖稱為無向完全圖

• 有向完全圖(Directed Complete Graph): 有向圖，邊的取值范圍是0到n(n-1)；邊數(shù)達到最大值n(n-1)條弧的有向圖稱為有向完全圖

• 稠密圖和稀疏圖： 在具有n個頂點，e條邊的圖G中， 如果含有的邊較少（`）,則稱圖G為稀疏圖，否則為稠密圖

• 子圖： 假設(shè)有兩個圖G=(V,{E}),和G' = (V',{E'}),如果V' 屬于V,E'屬于E,則稱G' 為G的子圖

6.3子示意圖.png

• 鄰接點： 假若頂點v 和頂點w 之間存在一條邊（或?。?， 則稱頂點v 和w 互為鄰接點。
• 頂點的度（Degree）：是圖中與該頂點相關(guān)聯(lián)邊的數(shù)目， 頂點V的度記為D(V)
• 入度和出度: 在有向圖中，以頂點V為終點的弧稱為入度,記為 ID(V);以頂點V為起點的弧稱為出度，記為 OD(V)；該頂點V的度為D(V) = ID(V) + OD(V)
• 所有頂點度和與邊數(shù)e的關(guān)系：`; 即所有頂點度的和為所有邊數(shù)的兩倍
• 路徑（Path）：在一個圖中，路徑是從頂點u到頂點v所經(jīng)過的頂點序列，即{u=v0,v1,...,vi=v}
• 路徑長度： 路徑上的邊數(shù)或弧的數(shù)目
• 回路（環(huán)）： 第一個頂點和最后一個頂點相同的路徑
• 初等路徑： 序列中頂點不重復(fù)出現(xiàn)的路徑
• 初等回路（環(huán)）：除第一個頂點和最后一個頂點之外，其余頂點不重復(fù)出現(xiàn)的回路
• 連通圖（Connected Graph）： 在無向圖中，從頂點u到到頂點v有路徑，則稱頂點u與頂點v連通，圖中任意兩個頂點連通，則稱該圖為連通圖

連通圖.png

• 連通分量(Connected Component)：無向圖中的極大連通子圖稱為連通分量

• 強連通圖：在有向圖中， 圖中任意兩個頂點連通，則稱該圖為強連通圖

強連通分量.png

• 強連通分量：有向圖中的極大連通子圖稱為強連通分量
• 強連通圖只有一個強連通分量，即其本身
• 生成樹： 是極小的連通子圖，它包含圖中全部n個頂點，但只有足以構(gòu)成一棵樹的n-1條邊
• 生成森林： 對于非連通圖，每個連通分量可形成一棵生成樹，這些生成樹組成了該非連通圖的生成森林。

二、圖的存儲結(jié)構(gòu)

1. 鄰接矩陣（Adjacency Matrix）：

• 鄰接矩陣：用來表示頂點之間的相鄰關(guān)系的矩陣

• 無向圖的鄰接矩陣是 對稱陣，可以采用壓縮存儲

• 有向圖的鄰接矩陣一般不對稱

• 使用鄰接矩陣存儲圖，所需要的存儲空間只與頂點數(shù)有關(guān)

• 頂點的度：

  • 在無向圖鄰接矩陣中，第i行或第i列的非零元素的個數(shù)正好是第i個頂點的度
  • 在有向圖鄰接矩陣中，第i行非零元素的個數(shù)正好是第i個頂點的出度，第i列非零元素的個數(shù)正好是第i個頂點的入度

• 示意圖

有向圖的鄰接矩陣.png

無向圖鄰接矩陣.png

• 鄰接矩陣 完整實現(xiàn)代碼

2. 鄰接表（Adjacency List）

1. 頂點的度:
   • 無向圖中，頂點的度等于該頂點鄰接表中邊結(jié)點的個數(shù), 如下圖頂點v1的度為2
   • 有向圖中，頂點的出度等于該頂點鄰接表中邊結(jié)點的個數(shù)；入度需要遍歷整個鄰接表或建立一個逆鄰接表； 如下圖的頂點v0, 由鄰接表知出度為1，逆鄰接表知入度為2

7-4-6無向圖鄰接表.png

7-4-7有向圖的鄰接表.png

• 對于n個頂點和e條邊的無向圖，其鄰接表有n個頂點和2e個邊結(jié)點
• 對于n個頂點和e條邊的有向圖，其鄰接表有n個頂點和e個邊結(jié)點
• 所以：對于稀疏圖，使用鄰接表比使用鄰接矩陣更省空間

2. 鄰接表 完整代碼

3. 圖的遍歷

1. 類型：

• 深度優(yōu)先遍歷（Depth_First_Search，DFS）, 類似樹的前序遍歷
• DFS.java

DFS遍歷的序列：01374256 .gif

• 廣度優(yōu)先遍歷（Breadth_First_Search, BFS）， 類似樹的層次遍歷
• BFS.java
  
  BFS遍歷的序列: 01234567 .gif

4. 最小生成樹(Spanning Tree) 可視化

概念：

• 一個有n個頂點的連通圖的生成樹只能有n-1條邊。
• 圖的生成樹不唯一，遍歷方法不同生成樹不同，遍歷起點不同生成樹不同
• 最小生成樹： 在一個網(wǎng)的所有生成樹中，權(quán)值綜合最小的生成樹稱為最小生成樹(Minimum Cost Spanning Tree)

構(gòu)造最小生成樹的準則：

1. 只能使用該圖中的邊構(gòu)造最小生成樹
2. 當且僅當使用n-1條邊連接圖中的n個頂點
3. 不能使用產(chǎn)生回路的邊

克魯斯卡爾算法(Kruskal)

1. 步驟：

• 假設(shè)圖G = (V,E)是一個具有n個頂點的連通無向圖，T = (V,TE)是網(wǎng)G的最小生成樹， V是T的頂點集，TE是T的邊集
• 一、 T的初始化狀態(tài)為T = (V, NULL), 即開始時，最小生成樹T是圖G的生成零圖
• 二、 將圖G中的邊按照權(quán)值從小到大的順序依次選取，若選取的邊未使生成樹T形成回路，則加入TE中，否則舍棄，直到TE中包含n-1 條邊為止

2. 示意圖

   
   
   6.15Kruskal's Algorithm.png

3. Kruskal.java 鄰接矩陣實現(xiàn)

普里姆算法（Prim）

1. 步驟：

• 假設(shè)圖G = (V,E)是一個具有n個頂點的連通圖，T = (U,TE)是網(wǎng)G的最小生成樹， U是T的頂點集，TE是T的邊集
• 一、從圖G中找一個頂點，作為開始點， 放入頂點集U中；頂點集U用來保存構(gòu)造最小生成樹的頂點
• 二、從頂點集U中所有頂點的鄰接點中，找出邊(不能構(gòu)成回路)上權(quán)最小的鄰接點；把權(quán)值最小的邊加入TE集合，相連的鄰接頂點加入頂點集合U中
• 三、重復(fù)步驟二，直到頂點集合U == V，則TE必定有n-1條邊，最小生成樹T構(gòu)造完畢

2. 示意圖

   
   
   6.16Prim's Algorithm.png

3. Prim.java 鄰接矩陣實現(xiàn)

5. 最短路徑

1. 最短路徑： 兩個頂點之間經(jīng)過的邊上權(quán)值之和最少的路徑； 路徑上第一個頂點稱為源點，最后一個頂點稱為終點
2. 迪杰斯特拉(Dijkstra) 算法

• 基本思想：
  1. 通過Dijkstra計算圖G中的最短路徑時，需要指定開始計算的頂點s
  2. 此外，還需要引進兩個集合S和U。S的作用是記錄已求出最短路徑的頂點(以及相應(yīng)的最短路徑長度)，而U則是記錄還未求出最短路徑的頂點(以及該頂點到起點s的距離)。
  3. 初始化時，把指定開始計算的頂點s加入集合S中；而集合U中是除s之外的頂點，并且U中頂點的路徑是起點s到該頂點的路徑。
  4. 然后，從U中找出路徑最短的頂點，并將其加入到S中；接著，更新U中的頂點和頂點對應(yīng)的路徑。
  5. 重復(fù)步驟4； 直到遍歷完所有頂點
• 圖解 (圖來自 skywang12345)
  
  Dijkstra's Algorithm.png
• 實現(xiàn)
  ShortestPath_Dijkstra.java

3. 弗洛依德(Floyd) 算法

• 基本思想

1. 通過Floyd計算圖G=(V,E)中各個頂點的最短路徑時，需要引入一個矩陣S，矩陣S中的元素a[i][j]表示頂點i(第i個頂點)到頂點j(第j個頂點)的距離。
2. 假設(shè)圖G中頂點個數(shù)為N，則需要對矩陣S進行N次更新。
3. 初始時，矩陣S中頂點a[i][j]的距離為頂點i到頂點j的權(quán)值；如果i和j不相鄰，則a[i][j]=∞。
4. 接下來開始，對矩陣S進行N次更新。
5. 第1次更新時，如果"a[i][j]的距離" > "a[i][0]+a[0][j]"(a[i][0]+a[0][j]表示"i與j之間經(jīng)過第1個頂點的距離")，則更新a[i][j]為"a[i][0]+a[0][j]"。同理，第k次更新時，如果"a[i][j]的距離" > "a[i][k]+a[k][j]"，則更新a[i][j]為"a[i][k]+a[k][j]"。更新N次之后，操作完成！

• 圖解

  
  
  ShortestPath_Floyd.png

• 參考 https://www.cnblogs.com/skywang12345/p/3711532.html

• ShortestPath_Floyd.java

6. 拓撲排序

• 概念：

1. 有向無環(huán)圖: 無環(huán)的有向圖稱為有向無環(huán)圖（Directed Acycline Grap,DAG）
2. 頂點活動網(wǎng)： 頂點表示活動，弧表示活動之間的優(yōu)先制約關(guān)系，稱為這種有向圖為頂點活動網(wǎng)（Activity On Vertex,AOV）
3. 判讀有向環(huán)：若AOV網(wǎng) 不能得到拓撲有序序列，則必定存在有向環(huán)

• 拓撲排序步驟：

1. 在AOV網(wǎng)中選擇一個沒有前驅(qū)的頂點輸出
2. 從AOV網(wǎng)中刪除該頂點以及從它出發(fā)的弧
3. 重復(fù)步驟1和2， 直到AOV網(wǎng)為空，，或者剩余子圖中不存在沒有前驅(qū)的頂點，后一種情況則說明該AOV網(wǎng)存在有向環(huán)。

• 圖解(圖來自)
  

  TopologicalSort.png

• 代碼實現(xiàn)
  TopologicalSort.java

7. 關(guān)鍵路徑

術(shù)語

1. AOE網(wǎng)：
   以頂點表示事件，弧代表活動，權(quán)表示活動需要的時間頂點表示以它為弧頭的所有弧代表的活動已完成，所有以它為弧尾的弧代表的活動可以開始
2. 源點和匯點：
   正常情況(無環(huán))下，網(wǎng)中只有一個入度為零的點,稱為源點
   一個出度為零的點,稱為匯點。
3. 關(guān)鍵路徑：
   完成整個工程的最短時間是從源點到匯點的最長路徑的長度(路徑長度等于路徑上各邊的權(quán)之和)
   這條具有最大長度的路徑稱為關(guān)鍵路徑
4. ee(i)：表示事件Vi的最早發(fā)生時間
5. le(i)：表示事件Vi的最遲發(fā)生時間；
6. e(k)：活動ak=<vi，vj>的最早開始時間
7. l(k)：活動ak=<vi，vj>的最遲開始時間;定義e(i)=l(i）的活動叫關(guān)鍵活動；
8. l(k)-e(k)：完成活動ak的時間余量

步驟

• 示意圖（來源網(wǎng)上）

  
  
  criticalpath.png

1. 求ee(j): 從源點V1出發(fā),令ee(V1)=0, 按照拓撲排序序列求其余各頂點的最早發(fā)生時間，ee(j) = max{ee(i)+ len<vi,vj>}; len<vi,vj>}是弧<vi,vj>上的權(quán)值；如：ee(V2) = ee(V1) + a1 = 0+6=6; ee(V5) = ee(v2) + a4 = 6+1=7
2. 求le(i): 從匯點出發(fā)，令 ，按照逆拓撲排序序列求其余頂點的最晚開始時間le(i); le(i) =min{ le(j)-len<vi,vj>}；len<vi,vj>}是弧<vi,vj>上的權(quán)值; 如：令le(V9)= ee(V9) = 18; le(V8) = le(V9) - a11 = 18-4 = 14;
3. 求每一項活動ai 的最早開始時間 e(i) = ee(j) 和最晚開始時間 l(i) = le(j) - len<vi,vj>;
   若e(i) == l(i) ,則為關(guān)鍵活動。如上圖： e(a1) = ee(V1) = 0, l(a1) = le(V1) - 0= 0; e(a2) = ee(V1) = 0 , l(a2) = le(V3) - a2 = 6-4=2

代碼實現(xiàn)

• CriticalPath.java