思維導(dǎo)圖：

?

?

?

?6.6.1 最小生成樹

### 6.6 圖的應(yīng)用

#### 主旨：圖的概念可應(yīng)用于現(xiàn)實生活中的許多問題，如網(wǎng)絡(luò)構(gòu)建、路徑查詢、任務(wù)排序等。

---

#### 6.6.1 最小生成樹

**概念**：要在n個城市中建立通信聯(lián)絡(luò)網(wǎng)，則最少需要n-1條線路。目標(biāo)是如何在最少的費用下建立這個通信網(wǎng)絡(luò)。

- **關(guān)鍵概念**：最小代價生成樹 (Minimum Cost Spanning Tree)，簡稱最小生成樹。

- **性質(zhì)(MST的性質(zhì))**：在一個連通網(wǎng)中，總會存在一條邊，它是連接兩個頂點集合的最小權(quán)值邊，并且這條邊屬于最小生成樹。

---

**普里姆(Prim)算法**

- **思想**：從一個初始頂點開始，每次選擇一個最小邊連接未連接的頂點。

1. **算法步驟**：
? ? - ①: 初始選擇一個頂點放入集合U，初始化closedge，保存每個點到集合U的最短距離。
? ? - ②: 重復(fù)n-1次，每次從closedge中選擇最小邊，加入結(jié)果集，并更新U和closedge。
? ??
2. **實現(xiàn)**：
? ? - 初始化：從給定的頂點u開始，初始化closedge。
? ? - 主循環(huán)：重復(fù)選擇最小的邊，并更新closedge直到所有的頂點都被加入。

3. **注意點**：
? ? - 當(dāng)存在多個相同權(quán)值的邊時，選擇任何一個都可以。
? ? - 普里姆算法的時間復(fù)雜度是O(n^2)，適合于稠密網(wǎng)。

---

#### 筆記總結(jié)：

- **重點**：最小生成樹是建立最小費用網(wǎng)絡(luò)的關(guān)鍵，其目標(biāo)是選擇邊，使得總權(quán)值最小。
- **難點**：理解MST性質(zhì)并應(yīng)用于普里姆算法的實現(xiàn)。
- **易錯點**：
? ? 1. 在更新closedge時，要確保只考慮未被選擇的頂點。
? ? 2. 在存在多個最小權(quán)值邊時，要能正確處理。

普里姆算法是求解最小生成樹問題的一種有效方法，它從一個頂點開始，每次選擇一個最小的邊擴展，直到所有的頂點都被包括在內(nèi)。

---

**6.1 最小生成樹的構(gòu)建方法**

**1. 普里姆算法 (Prim's Algorithm):**
- 初始狀態(tài): U={v}
- 過程:
? 1. 找到權(quán)值最小的邊 (v, v?) 作為生成樹的第一條邊。
? 2. 頂點 v? 并入集合 U 中。
? 3. 更新輔助數(shù)組的值。
? 4. 重復(fù)上述過程，直到 U=V。

**2. 克魯斯卡爾算法 (Kruskal's Algorithm):**
- 初始狀態(tài): 有 n 個頂點但無邊的非連通圖 T=(V,{})
- 過程:
? 1. 將 N 中的邊按權(quán)值從小到大排序。
? 2. 選擇權(quán)值最小的邊。如果這條邊的兩個頂點在不同的連通分量上，加入 T 中；否則選擇下一個最小權(quán)值的邊。
? 3. 重復(fù)上述步驟，直到 T 中所有的頂點都在同一個連通分量上。

**克魯斯卡爾算法的實現(xiàn):**
- 使用結(jié)構(gòu)體數(shù)組 Edge 來存儲邊的信息。
- 使用輔助數(shù)組 Vexset 來標(biāo)識各個頂點所屬的連通分量。

**算法描述:**
1. 對數(shù)組 Edge 中的元素按權(quán)值進(jìn)行排序。
2. 查看數(shù)組 Edge 中的邊，并對每條邊執(zhí)行以下操作：
? ?1. 從已排序的數(shù)組中選擇一條邊。
? ?2. 在 Vexset 中查找該邊兩端的頂點所在的連通分量，并進(jìn)行比較。

**算法分析:**
- 克魯斯卡爾算法適合稀疏網(wǎng)的最小生成樹構(gòu)建。
- 克魯斯卡爾算法的時間復(fù)雜度與網(wǎng)中的邊數(shù)有關(guān)。

---

我的理解：

讓我們嘗試使用圖像和比喻來解釋最小生成樹和普利姆算法。

### 最小生成樹

**比喻**：想象一個島嶼上有若干個村莊，這些村莊之間要鋪設(shè)道路使得所有村莊都相互連通。但由于資金有限，我們希望用最少的路程來實現(xiàn)這一目標(biāo)。

在這張圖中，紅色的圈代表村莊，線代表道路。這些道路形成了一個最小生成樹，使得所有村莊都連通，且總的路程最短。

### 普利姆算法

**比喻**：你正在為村莊鋪設(shè)道路。你選擇一個村莊作為起點，并查看與它相連的所有道路。你選擇最短的道路并鋪設(shè)它，然后再選擇下一個與已鋪設(shè)道路相連的最短道路，依此類推，直到所有村莊都與至少一條道路相連。

**圖像描述**：

在這張圖中，我們首先選擇左上角的村莊。虛線代表考慮鋪設(shè)的道路，而實線代表已經(jīng)鋪設(shè)的道路。按照普利姆算法，我們首先選擇左上和右上兩個村莊之間的道路（因為它是最短的），

6.6.2最短路徑

**6.6.2 最短路徑**

**定義**：在圖結(jié)構(gòu)中，最短路徑問題是為了找出兩個節(jié)點之間的最優(yōu)路徑，這可以是最短的、最快的、成本最少的等等。

**示例**：交通咨詢系統(tǒng)可以采用圖的結(jié)構(gòu)來表示實際的交通網(wǎng)。其中，頂點代表城市，而邊代表城市間的交通聯(lián)系。例如，如果一個旅客想從A城市到達(dá)B城市并選擇中轉(zhuǎn)次數(shù)最少的路線，則可以通過廣度優(yōu)先搜索找到從A到B所含邊數(shù)最少的路徑。

- 帶權(quán)圖：為了在圖上表示例如距離、所需時間或交通費用等信息，可以對邊賦予權(quán)值。此時，路徑的長度度量不再是路徑上的邊的數(shù)量，而是路徑上的邊的權(quán)值之和。

- 有向圖：考慮到例如上山和下山的汽車或順?biāo)湍嫠妮喆ㄙM的時間或費用不同，交通網(wǎng)通常用帶權(quán)有向網(wǎng)表示。在這樣的圖中，路徑上的第一個頂點稱為源點，而最后一個稱為終點。

本節(jié)主要討論兩種常見的最短路徑問題：

1. **單源點的最短路徑問題**：從指定的源點到圖中的其他所有頂點的最短路徑。
? ?
? ?- **Dijkstra算法**：由Dijkstra提出，它可以按路徑長度遞增的次序生成最短路徑。
? ? ?
? ? ?- **算法過程**：
? ? ? ?1. 將圖的頂點分為兩組：
? ? ? ? ? - S: 已經(jīng)找到最短路徑的終點集合（開始時只包含源點v?）。
? ? ? ? ? - V-S: 尚未找到最短路徑的頂點集合（開始時為V-{v?}）。
? ? ? ?2. 算法將逐漸將V-S中的頂點按與v?之間的最短路徑長度遞增的次序加入S集合。在此過程中，始終保持從v?到S中各頂點的路徑長度不超過到V-S中各頂點的路徑長度。

2. **所有頂點對的最短路徑問題**：求出圖中每對頂點之間的最短路徑。

**總結(jié)**：最短路徑問題是圖論中的一個經(jīng)典問題，對于實際應(yīng)用如交通咨詢系統(tǒng)、網(wǎng)絡(luò)路由等都有很大的實用價值。不同的算法適用于不同的場景和需求，如Dijkstra算法適用于求解單源點的最短路徑問題。

?我的理解：

---

**1. 最短路徑問題的比喻：**

**比喻**：想象一個大城市的地鐵系統(tǒng)。你現(xiàn)在處于A站，想要到達(dá)B站。這個城市的地鐵系統(tǒng)就像是一個大型圖，每個地鐵站就是圖中的一個頂點，每條地鐵線路則是圖中的一條邊。

在這個城市中，有些地鐵線路非?？?#xff0c;有些則非常慢。你的任務(wù)是找到從A站到B站的最短路徑，不僅僅是經(jīng)過的站數(shù)最少的路徑，還可能是時間最短的、或成本最低的路徑。

---

**2. 帶權(quán)圖：**

**比喻**：回到地鐵系統(tǒng)的例子，不同的地鐵線可能需要不同的時間。例如，從A站到C站可能需要10分鐘，而從A站到D站可能需要20分鐘。這個時間就是"權(quán)值"。

---

**3. 單源點的最短路徑問題：**

**比喻**：你在一個大商場的入口處（源點），想要找到到達(dá)所有其他店鋪（頂點）的最快路徑。

**Dijkstra算法**就像是一個智能助手，它先告訴你到達(dá)最近的店鋪的最快路徑，然后是第二近的，以此類推，直到你知道到達(dá)所有店鋪的最快路徑。

---

**4. 所有頂點對的最短路徑問題：**

**比喻**：想象你正在為一個送貨公司工作，公司的任務(wù)是將包裹從一個城市送到另一個城市。你需要為每一對城市之間找到最短的送貨路徑，以節(jié)省時間和成本。

這就像擁有一個全城的地圖，而不僅僅是從一個特定地點到其他地點的地圖。你的目標(biāo)是找到每對城市之間的最優(yōu)路徑。

---

總的來說，最短路徑問題就像是在復(fù)雜的網(wǎng)絡(luò)中找到最優(yōu)的路徑，這個網(wǎng)絡(luò)可以是地鐵系統(tǒng)、城市、商場或任何其他實際生活中的場景。而Dijkstra算法等工具就像是幫助你在這些網(wǎng)絡(luò)中導(dǎo)航的智能助手。

?

?

### 圖中的最短路徑問題：
1. **假設(shè)與證明**：
? ?- 假設(shè)集合S為已求得最短路徑的終點。
? ?- 下一條最短路徑的終點為x，路徑要么是邊(v.x)，要么經(jīng)過S中的頂點后到達(dá)x。
? ?- 用反證法證明：如果路徑上的頂點不在S中，則存在更短的不在S中的路徑，這與算法是遞增求最短路徑的方式矛盾。
??
2. **示例**：圖6.22為帶權(quán)有向圖G?，表6.2顯示從v?到其它頂點的最短路徑。

3. **迪杰斯特拉算法**：
? ?- **實現(xiàn)方式**：
? ? ?- 使用帶權(quán)的鄰接矩陣arcs表示有向網(wǎng)G，G.arcs[i][j]表示弧<v?,v?>上的權(quán)值。
? ? ?- 輔助數(shù)據(jù)結(jié)構(gòu)：
? ? ? ?1. 數(shù)組S[i]：標(biāo)記從源點v?到終點v?的最短路徑是否已確定。
? ? ? ?2. 數(shù)組Path[i]：記錄從v?到v?的最短路徑上v?的前驅(qū)頂點序號。
? ? ? ?3. 數(shù)組D[i]：記錄從v?到v?的當(dāng)前最短路徑長度。
??
? ?- **算法步驟**：
? ? ?1. 初始化：
? ? ? ? - 將源點v?加入S，設(shè)置S[v?]=true。
? ? ? ? - 設(shè)置源點到各點的最短路徑長度D[i]。
? ? ? ? - 設(shè)置前驅(qū)節(jié)點Path[i]。
? ? ?2. 主循環(huán)：
? ? ? ? - 循環(huán)n-1次，選擇最短路徑的終點v，加入S。
? ? ? ? - 更新從v?到集合V-S的所有頂點的最短路徑長度。
? ? ? ? - 若找到更短的路徑，更新前驅(qū)節(jié)點和路徑長度。
??
? ?- **算法描述**：
? ? ?- 函數(shù)ShortestPath DIJ(AMGraph G,int vo)使用Dijkstra算法計算從v?到其它頂點的最短路徑。
? ? ?- 初始化部分：包括設(shè)置源點、初始化最短路徑長度和前驅(qū)節(jié)點。
? ? ?- 主循環(huán)：尋找最短路徑并更新相關(guān)數(shù)據(jù)。

?

---

### 迪杰斯特拉(Dijkstra)算法

**目的**：求解從給定源點到所有其他頂點的最短路徑。

**主要思想**：
1. 初始化：選擇源點v?，設(shè)置距離數(shù)組D和路徑數(shù)組Path。
2. 重復(fù)n-1次：每次找到一個離v?最近的未訪問過的頂點，并更新其鄰接點的距離。
3. 結(jié)果：D數(shù)組記錄了從v?到所有其他頂點的最短距離，Path數(shù)組記錄了最短路徑信息。

**時間復(fù)雜度**：O(n2)

**注意**：即使你只想求解從源點到某一個特定頂點的最短路徑，該問題仍然需要與求解源點到所有其他頂點的最短路徑一樣的時間。

---

### 弗洛伊德(Floyd)算法

**目的**：求解圖中任意兩點之間的最短路徑。

**主要思想**：
1. 初始化：用帶權(quán)的鄰接矩陣arcs表示有向網(wǎng)G，設(shè)置距離矩陣D和路徑矩陣Path。
2. 通過引入中間頂點的方法，對所有頂點對的路徑進(jìn)行n次比較和更新。
3. 結(jié)果：D矩陣記錄了所有頂點對的最短距離，Path矩陣記錄了最短路徑信息。

**時間復(fù)雜度**：O(n3)

**注意**：盡管有兩種方法來求解每一對頂點之間的最短路徑（一是多次調(diào)用迪杰斯特拉算法，二是使用弗洛伊德算法），但弗洛伊德算法在形式上較為簡潔。

---

基于您提供的文本，以下是該段內(nèi)容的整理：

---

**弗洛伊德算法及其應(yīng)用**

**定義**：
圖中所有頂點對之間的最短路徑長度可以表示為一個n階方陣D。隨著算法的執(zhí)行，這個方陣的值會不斷變化，構(gòu)成一個n階方陣序列，可以表示為：D(-1), D(0), D(1), …, D(n-1)。

公式：
1. D[i][j] = G.arcs[i][j]
2. D[i][j] = min {D[i][k] + D[k][j]} (其中，0≤k≤n-1)

含義：
- D[i][j] 是從頂點 i 到頂點 j，中間頂點序號不大于 k 的最短路徑的長度。
- D"_[JU] 是從頂點 v 到頂點 v 的最短路徑的長度。

**弗洛伊德算法**:
算法的時間復(fù)雜度是 O(n3)。算法描述如下：

void ShortestPath_Floyd(AMGraph G) {// 初始化路徑和距離for(int i = 0; i < G.vexnum; ++i)for(int j = 0; j < G.vexnum; ++j) {D[i][j] = G.arcs[i][j];if(D[i][j] < MaxInt && i != j)Path[i][j] = i; ?// 如果 i 和 j 之間有弧，則將 j 的前驅(qū)置為 ielsePath[i][j] = -1; // 如果 i 和 j 之間無弧，則將 i 的前驅(qū)置為 -1}// 更新路徑和距離for(int k = 0; k < G.vexnum; ++k)for(int i = 0; i < G.vexnum; ++i)for(int j = 0; j < G.vexnum; ++j)if(D[i][k] + D[k][j] < D[i][j]) {D[i][j] = D[i][k] + D[k][j];Path[i][j] = Path[k][j];}
}

**示例**:
圖6.24表示帶權(quán)有向圖G，其鄰接矩陣在圖6.25中給出。對此圖應(yīng)用弗洛伊德算法得到的各頂點對之間的最短路徑及其路徑長度的變化在表6.5中顯示。

**如何從表6.5中讀取兩個頂點之間的最短路徑**:
以Path3)為例，從D3)知，頂點1到頂點2的最短路徑長度為8，最短路徑中頂點2的前驅(qū)是頂點3；再查看Path[1][3]得知，頂點3的前驅(qū)是頂點1。所以，從頂點1到頂點2的最短路徑為 {<1,3>,<3,2>}。

---

?6.6.3 拓?fù)渑判?/h2>

**6.6.3 拓?fù)渑判?*

---

**1. AOV-網(wǎng)與有向無環(huán)圖**
- **定義**：無環(huán)的有向圖稱作有向無環(huán)圖(Directed Acyclic Graph)，簡稱DAG圖。
- **應(yīng)用**：DAG圖是描述一項工程或系統(tǒng)進(jìn)行過程的有效工具，如計劃、施工、生產(chǎn)流程和程序流。
- **活動與約束**：工程通常分為若干子工程(稱作活動)，子工程間存在優(yōu)先關(guān)系。例如，某些子工程開始前需要另一些子工程完成。

? ?*示例*：軟件專業(yè)學(xué)生需要學(xué)習(xí)一系列課程，其中部分課程要在先修課程后學(xué)習(xí)。

? ?如：課程之間的關(guān)系可以用有向圖表示。

- **AOV-網(wǎng)定義**：有向圖中，頂點表示活動，有向弧表示活動間的優(yōu)先關(guān)系稱為AOV-網(wǎng)。若存在有向環(huán)，則表示存在邏輯錯誤(如工程中某活動以自己為先決條件，或程序中存在死循環(huán))。

**2. 拓?fù)渑判蚨x與過程**
- **定義**：拓?fù)渑判蚴菍OV-網(wǎng)中的所有頂點排成線性序列，滿足：如果從頂點v到頂點v'有路徑，則v必定在v'之前。

- **拓?fù)渑判虿襟E**：
? 1. 選擇一個無前驅(qū)的頂點并輸出。
? 2. 刪除該頂點及所有以它為尾的弧。
? 3. 重復(fù)步驟1和2，直至所有頂點都輸出。
? 4. 若輸出的頂點數(shù)小于有向圖中的頂點數(shù)，說明存在環(huán)。

? ?*示例*：圖6.27展示了一個有向圖的拓?fù)渑判蜻^程，得到拓?fù)溆行蛐蛄袨?Vs,V?,V?,V?,Vz,Vs。

**3. 拓?fù)渑判虻膶崿F(xiàn)**
- **數(shù)據(jù)結(jié)構(gòu)**：
? 1. **鄰接表**：用于存儲有向圖。
? 2. **一維數(shù)組indegree[]**：存放每個頂點的入度。無前驅(qū)的頂點入度為0。

- **算法**：
? 1. 初始化所有頂點的入度。
? 2. 找到入度為0的頂點，輸出。
? 3. 刪除該頂點及與其相關(guān)的弧，即將所有與該頂點相鄰的頂點入度減1。
? 4. 重復(fù)步驟2和3，直到所有頂點都輸出或不存在入度為0的頂點。

? ?*注意*：在實際操作中，不需要真正刪除頂點或弧，只需調(diào)整相關(guān)頂點的入度。

---

**總結(jié)**：拓?fù)渑判蚴菍τ邢驘o環(huán)圖進(jìn)行排序的方法，確保每個活動在其前驅(qū)活動之后。這對于任務(wù)調(diào)度、項目計劃和課程規(guī)劃等應(yīng)用都是非常有用的。

我的理解：

我們可以使用“修建一座城堡”作為比喻來解釋這一節(jié)的內(nèi)容。

---

**修建一座城堡：拓?fù)渑判虻谋扔?*

想象你要修建一座宏偉的城堡。城堡不是一下子就修好的，你需要按照特定的步驟和順序完成，例如先挖地基、然后建墻、接著建塔樓等等。這些步驟就像是你所學(xué)習(xí)的各個課程，某些步驟是其他步驟的前提。

1. **城堡的各個部分 = DAG圖中的活動**
? ?- 城墻、塔樓、大門、護(hù)城河等每個部分都是一個活動，有些部分需要在其他部分之前完成。例如，你不能在沒有地基的情況下建墻。

2. **先決條件 = 活動間的優(yōu)先關(guān)系**
? ?- 你不能在護(hù)城河還沒挖好的情況下建橋。同樣地，你不能在地基還沒打好的情況下建墻。這些都是先決條件或優(yōu)先關(guān)系。

3. **拓?fù)渑判?= 建筑計劃**
? ?- 當(dāng)你開始建造城堡時，你需要一個清晰的計劃，告訴你哪一部分應(yīng)該首先建造，接下來是什么，直到整個城堡完成。拓?fù)渑判蚓拖袷沁@個建筑計劃，確保你不會因為順序錯誤而陷入困境。

4. **找出無前驅(qū)的活動 = 選擇可以立即開始的工作**
? ?- 在整個建筑計劃中，首先找到哪些部分是可以立即開始的（比如挖地基）。這就像找到一個沒有先修課程要求的新課程。

5. **刪除某活動及其連接 = 完成某部分工作并前進(jìn)**
? ?- 當(dāng)你完成了某部分（比如地基），你就可以考慮下一步要做什么，并且確定你已經(jīng)完成的工作不會再次干擾你。在拓?fù)渑判蛑?#xff0c;這就是刪除一個頂點及其相關(guān)的弧。

6. **環(huán)的存在 = 邏輯錯誤**
? ?- 如果你發(fā)現(xiàn)在建筑計劃中某個部分依賴于它自身或形成了一個循環(huán)依賴，那就意味著計劃中有一個邏輯錯誤。這就像在DAG中發(fā)現(xiàn)了一個環(huán)。

---

所以，拓?fù)渑判蚓拖袷切藿ǔ潜さ牟襟E，確保每個部分都在正確的時間和順序中建造，使整個城堡穩(wěn)固且宏偉。

?拓?fù)渑判蚣八惴?*

- **定義與工具**:
? - **棧S**: 暫存所有入度為0的頂點。避免重復(fù)查找數(shù)組indegree[]，提高效率。
? - **一維數(shù)組topo[i]**: 記錄拓?fù)湫蛄械捻旤c序號。
? - **算法6.12**: 拓?fù)渑判蛩惴枋觥?/strong>

- **算法步驟**:
? 1. 求出各頂點的入度并存入數(shù)組indegree[]，使入度為0的頂點入棧。
? 2. 當(dāng)棧不空時重復(fù)以下操作：
? ? ?- 使棧頂頂點v出棧并保存在拓?fù)湫蛄袛?shù)組topo中；
? ? ?- 對頂點v的每個鄰接點v的入度減1，如果v的入度變?yōu)?,則使v入棧。
? 3. 如果輸出頂點個數(shù)少于AOV-網(wǎng)的頂點個數(shù)，則網(wǎng)中存在有向環(huán)，無法進(jìn)行拓?fù)渑判?#xff0c;否則拓?fù)渑判虺晒Α?/strong>

- **算法描述**:
? 1. 初始化一個空的棧S。
? 2. 求各頂點入度并存入數(shù)組indegree中。
? 3. 入度為0的頂點入棧。
? 4. 當(dāng)棧非空時，重復(fù)以下操作：
? ? ?- 棧頂頂點v出棧并保存在數(shù)組topo中；
? ? ?- 遍歷頂點v的所有鄰接點，并對其入度減1；
? ? ?- 如果鄰接點入度減為0,則入棧。
? 5. 如果輸出頂點個數(shù)不等于AOV-網(wǎng)的頂點個數(shù)，則返回錯誤；否則，返回成功。

- **算法分析**:
? - 對于有n個頂點和e條邊的有向圖:
? ? - 建立求各頂點入度的時間復(fù)雜度為O(e)。
? ? - 建立零入度頂點棧的時間復(fù)雜度為O(n)。
? ? - 在拓?fù)渑判蛑?#xff0c;每個頂點進(jìn)棧、出棧一次，入度減1的操作總共執(zhí)行e次?？偟臅r間復(fù)雜度為O(n+e)。

- **應(yīng)用**:
? - 該拓?fù)渑判蛩惴ㄊ乔箨P(guān)鍵路徑算法的基礎(chǔ)。

---?

?

?6.6.4 關(guān)鍵路徑

---

**2. 關(guān)鍵路徑求解過程**

- **步驟概述：**
? 1. 對頂點排序并計算每個事件的最早發(fā)生時間 \( ve(i) \)。
? 2. 依據(jù)逆拓?fù)湫蛄杏嬎忝總€事件的最遲發(fā)生時間 \( vl(i) \)。
? 3. 計算每個活動 \( a \) 的最早開始時間 \( e(i) \)。
? 4. 計算每個活動 \( a \) 的最晚開始時間 \( l(i) \)。
? 5. 確定關(guān)鍵活動和關(guān)鍵路徑。

- **計算詳解：**

? 1. **計算最早發(fā)生時間**:
? ? ?- \( Ve(0) = 0 \)
? ? ?- \( ve(1) = max\{ve(0) + wa_1\} \)
? ? ?- \( ve(2) = max\{ve(0) + wo_2\} \)
? ? ?- ...
??
? 2. **計算最遲發(fā)生時間**:
? ? ?- \( vl(8) = ve(8) \)
? ? ?- \( vl(7) = min\{vl(8) - w_7s\} \)
? ? ?- ...
??
? 3. **計算最早開始時間**:
? ? ?- \( e(a_1) = ve(0) \)
? ? ?- \( e(a_2) = ve(0) \)
? ? ?- ...

? 4. **計算最晚開始時間**:
? ? ?- \( l(a_1) = vl(8) - w_7s \)
? ? ?- \( l(a_2) = vl(8) - w_6g \)
? ? ?- ...
??
? 5. **確定關(guān)鍵活動和關(guān)鍵路徑**:
? ? ?- 通過比較每個活動的最早開始時間和最晚開始時間來確定關(guān)鍵活動。關(guān)鍵路徑是由關(guān)鍵活動組成的路徑，從源點到匯點。

- **實例分析：** 通過圖6.28的AOE網(wǎng)來確定關(guān)鍵路徑。

? 1. **關(guān)鍵路徑結(jié)果：**
? ? ?- 圖6.28的AOE網(wǎng)有兩條關(guān)鍵路徑，如圖6.29所示。

- **關(guān)鍵路徑算法的實現(xiàn)：**
??
? 1. **前提**：關(guān)鍵路徑算法是基于拓?fù)渑判蛩惴ā?br /> ? 2. **數(shù)據(jù)結(jié)構(gòu)**：
? ? ?- 一維數(shù)組 \( ve[i] \) 表示事件 \( v_i \) 的最早發(fā)生時間。
? ? ?- 一維數(shù)組 \( vl[i] \) 表示事件 \( v_i \) 的最遲發(fā)生時間。
? ? ?- 一維數(shù)組 \( topo[i] \) 記錄拓?fù)湫蛄械捻旤c序號。

? 3. **算法步驟**：
? ? ?1. 調(diào)用拓?fù)渑判蛩惴ā?br /> ? ? ?2. 初始化每個事件的最早發(fā)生時間為0。
? ? ?3. 根據(jù)拓?fù)湫蛄?#xff0c;計算每個事件的最早發(fā)生時間。
? ? ?4. 初始化每個事件的最遲發(fā)生時間為匯點的最早發(fā)生時間。
? ? ?5. 根據(jù)逆拓?fù)湫蛄?#xff0c;計算每個事件的最遲發(fā)生時間。

---

【筆記】

**關(guān)鍵路徑算法筆記**

1. **目標(biāo)**: 判斷某一活動是否為關(guān)鍵活動。

2. **步驟**:
? ?- 調(diào)用拓?fù)渑判蛩惴ā?br /> ? ?- 使用拓?fù)浯涡蚯竺總€事件的最早發(fā)生時間。
? ?- 使用逆拓?fù)浯涡蚯竺總€事件的最遲發(fā)生時間。
? ?- 判斷每一活動是否為關(guān)鍵活動。

3. **核心代碼解析**:
? ?- 初始化：對于每個事件的最早發(fā)生時間置初值為0。
? ?- 使用拓?fù)浯涡蚋旅總€事件的最早發(fā)生時間。
? ?- 對于每個事件的最遲發(fā)生時間置初值為最后一個事件的最早發(fā)生時間。
? ?- 使用逆拓?fù)浯涡蚋旅總€事件的最遲發(fā)生時間。
? ?- 判斷活動的最早和最遲開始時間是否相等，相等則為關(guān)鍵活動，并輸出。

4. **算法分析**:
? ?- 時度為O(n+e)，其中n是頂點數(shù)，e是邊數(shù)。

5. **實際應(yīng)用**:
? ?- AOE網(wǎng)在估算工程完成時間上很有用。
? ?- 活動時間的調(diào)整可能會影響關(guān)鍵路徑，所以在調(diào)整時需要重新計算關(guān)鍵路徑。
? ?- 若有多條關(guān)鍵路徑，提高一條關(guān)鍵路徑上活動的進(jìn)度不能保證整個工程的工期縮短。

**六度空間理論**:

1. **概念**: 六度空間理論提出，在人際關(guān)系網(wǎng)絡(luò)中，任何兩個人之間都可以通過五個或更少的中間人聯(lián)系在一起。

2. **實驗**:
? ?- 由美國哥倫比亞大學(xué)社會學(xué)系的登肯·瓦茲(Duncan J.Watts)主持。
? ?- 166個國家，6萬多名志愿者參與。
? ?- 志愿者選擇目標(biāo)并發(fā)送郵件給可能知道目標(biāo)的親友。
? ?- 結(jié)果顯示郵件平均通過5-7個人達(dá)到目標(biāo)。

3. **結(jié)論**: 雖然該理論未得到嚴(yán)格證明，但多次實驗驗證了其合理性。

---

**六度空間理論的研究方法局限性**

1. **電子郵件研究的局限性**:
? ?- **人群局限性**: 僅有部分人群使用電子郵件保持社交關(guān)系。
? ?- **研究工程量大**: 需要跟蹤和記錄所有電子郵件的走向，需要大量的人力和時間。
? ?- **依賴志愿者**: 驗證過程與志愿者的積極性有關(guān)，可能會遺漏某些相識的人。

2. **現(xiàn)代通信方式**:
? ?- 電話和短信是現(xiàn)代人主要的聯(lián)系方式，其使用頻率遠(yuǎn)高于電子郵件。
? ?- 相對于電子郵件，電話和短信的通信更易于跟蹤，因為都有運營商記錄。
? ?- 可以設(shè)定條件定義“認(rèn)識”的關(guān)系，例如一年內(nèi)電話或短信往返兩次及以上。
? ?- 由于通信數(shù)據(jù)保密，我們不能獲取實際的通信數(shù)據(jù)，所以只能理論上分析。

3. **六度空間理論的圖論模型**:
? ?- 將人際關(guān)系網(wǎng)絡(luò)圖抽象成不帶權(quán)值的無向圖G。
? ?- 在圖G中，一個頂點代表一個人，一條邊代表兩個人之間的“認(rèn)識”關(guān)系。

---

這部分筆記主要強調(diào)了研究六度空間理論時使用電子郵件的局限性，并提到了現(xiàn)代通信方式如何可能更好地驗證這一理論。然后簡要描述了將人際關(guān)系轉(zhuǎn)化為圖論模型的方式。

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?總結(jié)：

**圖的應(yīng)用總結(jié)**

---

**重點**:

1. **表示與存儲**:
? ?- 鄰接矩陣、鄰接表、邊數(shù)組等是常用的圖的存儲結(jié)構(gòu)。
? ?
2. **遍歷**:
? ?- 深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(BFS)是兩種基本的圖遍歷算法。

3. **最短路徑**:
? ?- Dijkstra算法和Floyd-Warshall算法常用于求解加權(quán)圖的最短路徑問題。

4. **最小生成樹**:
? ?- Prim算法和Kruskal算法用于求無向加權(quán)圖的最小生成樹。

5. **拓?fù)渑判?*:
? ?- 用于有向無環(huán)圖（DAG），可幫助確定任務(wù)執(zhí)行的順序。

6. **強連通分量**:
? ?- Kosaraju和Tarjan算法用于找有向圖的強連通分量。

7. **網(wǎng)絡(luò)流**:
? ?- Ford-Fulkerson和Edmonds-Karp算法用于求最大流。

---

**難點**:

1. **算法的理解與實現(xiàn)**:
? ?- 例如Dijkstra的貪心思想，Floyd-Warshall的動態(tài)規(guī)劃思想。
? ?
2. **復(fù)雜數(shù)據(jù)結(jié)構(gòu)的應(yīng)用**:
? ?- 如優(yōu)先隊列在Dijkstra中，不相交集數(shù)據(jù)結(jié)構(gòu)在Kruskal中。

3. **無向圖與有向圖**:
? ?- 對于某些問題，如最小生成樹，僅限于無向圖。

4. **邊界情況的處理**:
? ?- 如帶權(quán)圖中的負(fù)權(quán)邊。

---

**易錯點**:

1. **未初始化**:
? ?- 如在Dijkstra中，需要初始化源頂點的距離為0，其他頂點的距離為無窮大。

2. **循環(huán)條件忽視**:
? ?- 在BFS和DFS中，可能未正確檢查節(jié)點是否已訪問。

3. **誤解數(shù)據(jù)結(jié)構(gòu)**:
? ?- 錯誤地將鄰接表用于需要鄰接矩陣的場景，反之亦然。

4. **忽略負(fù)權(quán)邊**:
? ?- 使用Dijkstra算法時，負(fù)權(quán)邊可能導(dǎo)致錯誤的結(jié)果。

5. **拓?fù)渑判蛑械沫h(huán)**:
? ?- 如果圖中存在環(huán)，則無法進(jìn)行拓?fù)渑判?#xff0c;但容易忽略這點檢查。

6. **空間與時間復(fù)雜度**:
? ?- 選擇不合適的算法或數(shù)據(jù)結(jié)構(gòu)可能導(dǎo)致效率低下。

---