系列文章目錄

目錄

• 圖的遍歷
• • 深度優(yōu)先遍歷
  • • 遞歸算法
    • 堆棧算法
  • 廣度優(yōu)先搜索
• 拓撲排序
• • 定義定理
  • 算法思想
  • 偽代碼
• 關鍵路徑
• • 基本概念
  • 關鍵活動有關量
  • 數(shù)學公式
  • 偽代碼
  • 時間復雜性

---

圖的遍歷

• 從給定連通圖的某一頂點出發(fā)，沿著一些邊訪問遍圖中所有的頂點，且使每個頂點僅被訪問一次，稱為圖的遍歷（Graph Traversal）
• 存在的問題：圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能會沿著某些邊又回到曾經(jīng)訪問過的頂點。
  • 避免重復訪問：設置一個標志頂點是否被訪問過的輔助數(shù)組 visited[]，它的初始狀態(tài)為 0。在圖的遍歷過程中，一旦某一個頂點 $i$ 被訪問，就立即讓 visited[i] 置為 1，防止它被多次訪問

深度優(yōu)先遍歷

• 深度優(yōu)先遍歷又被稱為深度優(yōu)先搜索 DFS (Depth First Search)，其類似于樹的先根遍歷
• 基本思想：
  • DFS在訪問圖中某一起始頂點 $v$ 后，由 $v$ 出發(fā)，訪問它的任一鄰接頂點 $w_1$；再從 $w_1$ 出發(fā)，訪問與 $w_1$ 鄰接但還沒有訪問過的頂點 $w_2$；然后再從 $w_2$ 出發(fā)，進行類似的訪問。如此往下去，直至到達所有的鄰接頂點都被訪問過的頂點 $u$ 為止。接著，退回一步，退到前一次訪問過的頂點，看看還有其它沒有被訪問的鄰接頂點。如果有，則訪問此頂點，之后再從此頂點出發(fā)，進行與前述類似的訪問；如果沒有，就再退回一步進行搜索。重復上述過程，直到連通圖中所有頂點都被訪問過為止
    

遞歸算法

偽代碼

// 圖的深度優(yōu)先遍歷的遞歸算法
DepthFirstSearch(v, visited)
{visited[v] = 1;p = adjacent(Head[v]);while (p != NULL){if (visited[VerAdj(p) != 1]){DepthFirstSearch(VerAdj(p), visited)p = link(p);	}}
}// 算法主體
DFS_Main()
{// 為輔助數(shù)組申請空間visited = new int[graphsize];// 數(shù)組初始化for (int k = 0; k < graphsize; k++){visited[k] = 0;// 從序號為0的頂點出發(fā)，深度優(yōu)先遍歷圖DepthFirstSearch(0, visited)delete[] visited;}
}

非連通圖需要多次調(diào)用深度優(yōu)先遍歷算法

for i = 0 to n-1
{for j = 0 to n-1{if visited[j] = 0{DepthFirstSearch(v[j], visited)}}	
}

算法分析

• 圖中有 $n$ 個頂點，$e$ 條邊
• 如果用鄰接表存儲，沿頂點的adjacent可以找到某個頂點 $v$ 的所有鄰接頂點 $w$。由于總共有 $2e$（無向圖）或 $e$（有向圖）個邊結(jié)點，所以掃描邊的時間為 $O(e)$。而且對所有頂點遞歸訪問 1 次，所以遍歷圖的時間復雜性為 $O(n+e)$
• 如果用鄰接矩陣存儲，則查找每一個頂點的所有的邊，所需時間為 $O(n)$，則遍歷圖中所有的頂點所需的時間為 $O(n^2)$

堆棧算法

• 可以利用堆棧實現(xiàn)深度優(yōu)先遍歷的非遞歸算法
• 堆棧中存放已訪問結(jié)點的還沒有被訪問的鄰接頂點。每次彈出棧頂元素時，如其未被訪問則訪問該頂點，檢查當前頂點的邊鏈表，將還沒有被訪問的鄰接頂點入棧，循環(huán)進行

基本思想
首先將所有頂點的visited[]值置為 0，初始頂點壓入堆棧

• ① 檢測堆棧是否為空。若堆棧為空，則迭代結(jié)束；否則，從棧頂彈出一個頂點 $v$
• ② 如果 $v$ 未被訪問過，則訪問 $v$，將visited[v]值更新為 1，然后根據(jù) $v$ 的鄰接頂點表，將 $v$ 的未被訪問的鄰接頂點壓入棧，執(zhí)行步驟 ①

// 非遞歸實現(xiàn)深度優(yōu)先遍歷算法
void DFS(Graph &graph, int v) {stack<int> S;         // 創(chuàng)建棧Svector<bool> visited(graph.size(), false); // 初始化訪問標記數(shù)組S.push(v);            // 將起始頂點壓入棧while (!S.empty()) {  // 當棧不為空時int v = S.top();  // 彈出棧頂元素S.pop();if (!visited[v]) {cout << v << " ";  // 訪問頂點visited[v] = true; // 標記為已訪問// 獲取頂點v的所有鄰接頂點，并壓入棧中for (auto p = graph.adjacent(v); p != nullptr; p = p->link) {if (!visited[p->VerAdj]) {S.push(p->VerAdj);}}}}
}

算法分析

• 如果使用鄰接表表示圖，則循環(huán)的總時間代價為 $d_0+d_1+?+d_{n?1}=O(e)$，其中 $d_i$ 是頂點 $i$ 的度（無向圖）或出度（有向圖）。總的時間復雜度為 $O(n+e)$
• 如果使用鄰接矩陣，則對于每一個被訪問的頂點，循環(huán)要檢測矩陣中的 $n$ 個元素，總的時間代價為 $O(n^2)$

---

廣度優(yōu)先搜索

• 為了實現(xiàn)逐層訪問，算法中使用了一個隊列，以記憶正在訪問的這一層和上一層的頂點，以便于向下一層訪問
• 與深度優(yōu)先搜索過程一樣，為避免重復訪問，需要一個輔助數(shù)組visited[]，為被訪問過的頂點加標記

// BFS1 [初始化]
CREATEQ(Q);         // 創(chuàng)建隊列 Q
for (int i = 1; i <= n; i++) visited[i] = 0; // 初始化所有頂點為未訪問
PRINT(v);           // 打印起始頂點
visited[v] = 1;     // 標記起始頂點為已訪問
Q.enqueue(v);       // 起始頂點入隊列// BFS2 [廣度優(yōu)先遍歷]
while (!Q.isEmpty()) {       // 當隊列不為空時v = Q.dequeue();         // 隊頭元素出隊p = adjacent(Head[v]);   // 獲取當前頂點的鄰接鏈表while (p != NULL) {      // 遍歷鄰接鏈表if (visited[p->VerAdj] == 0) { // 如果鄰接頂點未被訪問Q.enqueue(p->VerAdj);      // 將鄰接頂點入隊PRINT(p->VerAdj);          // 打印鄰接頂點visited[p->VerAdj] = 1;    // 標記鄰接頂點為已訪問}p = p->link;        // 繼續(xù)訪問下一個鄰接頂點}
}

算法分析

• 如果使用鄰接表表示圖，則循環(huán)的總時間代價為 $d_0+d_1+?+d_{n?1}=O(e)$，其中 $d_i$ 是頂點 $i$ 的度?？偟臅r間復雜度為 $O(n+e)$
• 如果使用鄰接矩陣，則對于每一個被訪問的頂點，循環(huán)要檢測矩陣中的 $n$ 個元素，總的時間代價為 $O(n^2)$

---

拓撲排序

• AOV 網(wǎng)：在有向圖中，用頂點表示活動，用有向邊表示活動之間的先后關系，稱這樣的有向圖為AOV網(wǎng) (Activity On Vertex Network)}
  • 計劃、施工過程、生產(chǎn)流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分為若干個叫做“活動”的子工程。完成了所有這些活動，這個工程就可以完成了
  • 例如，計算機專業(yè)學生的學習就是一個工程，每一門課程的學習就是整個工程的一些活動。其中有些課程要求先修課程，有些則不要求。這樣，在有些課程之間有先后關系，有些課程可以并行地學習

定義定理

• 在 AOV 網(wǎng)絡中，如果活動 $V_i$ 必須在活動 $V_j$ 之前進行，則存在有向邊 $?V_i,V_j?$
• AOV 網(wǎng)絡中不能出現(xiàn)有向回路，即有向環(huán)。在 AOV 網(wǎng)絡中如果出現(xiàn)了有向環(huán)，則意味著某項活動應以自己作為先決條件。因此，對給定的 AOV 網(wǎng)絡，必須先判斷它是否存在有向環(huán)
• 拓撲序列：AOV 網(wǎng)中所有頂點排成的線性序列，要求每個活動的所有前驅(qū)活動都排在該活動前面
• 拓撲排序：構造 AOV 網(wǎng)的拓撲序列的過程被稱為拓撲排序
• 如果通過拓撲排序能將 AOV 網(wǎng)絡的所有頂點都排入一個拓撲有序的序列中，則該 AOV 網(wǎng)絡中必定不會出現(xiàn)有向環(huán)；相反，如果得不到滿足要求的拓撲有序序列，則說明 AOV 網(wǎng)絡中存在有向環(huán)，此 AOV 網(wǎng)絡所代表的工程是不可行的
• 設圖 $G=(V,E)$ 是非循環(huán)圖，$V(G)\ne ?$，則 $G$ 中一定存在入度為零的頂點。
• 設 $G=(V,E)$ 是非循環(huán)圖， V ( G ) = { 1 , 2 , … , n } V(G) = \{1, 2, \dots, n\} V(G)={1,2,…,n}，$e=|E(G)|$。則算法是正確的，且算法的時間復雜性為 $O(n+e)$

算法思想

• 拓撲排序算法的基本步驟
  • 從網(wǎng)中選擇一個入度為 0 的頂點并將其輸出
  • 從網(wǎng)中刪除該頂點及其所有出邊
  • 執(zhí)行步驟 ① 和 ②，直至所有頂點都已輸出，或網(wǎng)中剩余頂點入度均不為 0（說明網(wǎng)中存在回路，無法繼續(xù)拓撲排序）
    注意：對于任何無回路的 AOV 網(wǎng)，其頂點均可排成拓撲序列，但其拓撲序列未必唯一

偽代碼

• 假定 AOV 網(wǎng)用鄰接表的形式存儲。為實現(xiàn)拓撲排序算法，事先需做好兩項準備工作：
• 建立一個數(shù)組count[]，count[i]的元素值為頂點 $i$ 的入度；
• 建立一個堆棧，棧中存放入度為 0 的頂點，每當一個頂點的入度為 0，就將其壓入棧

// TOrder1 [初始化]
// 計算 count 數(shù)組（每個頂點的入度）
for (int i = 1; i <= n; i++) count[i] = 0; // 初始化所有頂點的入度為 0// 遍歷鄰接表，計算每個頂點的入度
for (int i = 1; i <= n; i++) {p = adjacent(Head[i]); // 獲取頂點 i 的鄰接表頭指針while (p != NULL) {    // 遍歷鄰接表count[VerAdj(p)]++; // 更新鄰接頂點的入度p = p->link;        // 移動到下一個鄰接點}
}// 拓撲排序
top = 0; // 棧頂指針初始化為 0// 將入度為 0 的頂點壓入棧
for (int i = 1; i <= n; i++) {if (count[i] == 0) {stack[top] = i; // 頂點 i 入棧top++;          // 棧頂指針加 1}
}for (int i = 1; i <= n; i++) {// 如果循環(huán)體執(zhí)行了 n 次但棧為空，則說明圖中存在回路if (top == 0) {PRINT("There is a cycle in the network!");RETURN;} else {// 棧頂元素出棧j = stack[top - 1];top--; // 棧頂指針減 1PRINT(j); // 輸出頂點 j（拓撲序中的一個頂點）// 遍歷頂點 j 的鄰接表，更新鄰接頂點的入度p = adjacent(Head[j]);while (p != NULL) {k = VerAdj(p);    // 獲取鄰接頂點count[k]--;       // 鄰接頂點的入度減 1if (count[k] == 0) { // 如果鄰接頂點入度變?yōu)?0，則壓入棧stack[top] = k;top++;}p = p->link; // 繼續(xù)遍歷下一個鄰接點}}
}

---

關鍵路徑

基本概念

• 如果在有向無環(huán)的帶權圖中

  • 用有向邊表示一個工程中的各項活動 (Activity)
  • 用邊上的權值表示活動的持續(xù)時間 (Duration)
  • 用頂點表示事件 (Event)

• 則這樣的有向圖叫做用邊表示活動的網(wǎng)絡，簡稱AOE (Activity On Edges) 網(wǎng)絡

  • 源點：表示整個工程的開始（入度為零）
  • 匯點：表示整個工程的結(jié)束（出度為零）

• 在 AOE 網(wǎng)絡中，有些活動必須順序進行，有些活動可以并行進行

• 從源點到各個頂點，以至從源點到匯點的有向路徑可能不止一條。這些路徑的長度也可能不同。完成不同路徑的活動所需的時間雖然不同，但只有各條路徑上所有活動都完成了，整個工程才算完成

• 完成整個工程所需的時間取決于從源點到匯點的最長路徑長度，即在這條路徑上所有活動的持續(xù)時間之和。這條路徑長度最長的路徑被稱為關鍵路徑 (Critical Path)

• 關鍵路徑：從源點到匯點具有最大長度的路徑稱為關鍵路徑

• 路徑長度：指路徑上的各邊權值之和

• 關鍵活動：關鍵路徑上的活動

關鍵活動有關量

• 事件 $v_j$ 的最早發(fā)生時間ve(j)：

  • 從源點 $v_0$ 到 $v_j$ 的最長路徑長度。

• 事件 $v_j$ 的最遲發(fā)生時間vl(j)：

  • 保證匯點的最早發(fā)生時間不推遲（即不推遲整個工程完成時間）的前提下，事件 $v_j$ 允許的最遲發(fā)生時間，等于ve(n-1)減去從 $v_j$ 到 $v_{n?1}$ 的最長路徑長度

• 活動 $a_i$ 的最早開始時間e(i)：

  • 設活動 $a_i$ 在有向邊 $?v_j,v_k?$ 上，e(i)是從源點 $v_0$ 到 $v_j$ 的最長路徑長度。因此e(i) = ve(j)

• 活動 $a_i$ 的最遲開始時間l(i)：

  • l(i)是在不會引起時間延誤的前提下，該活動允許的最遲開始時間。設活動 $a_i$ 在有向邊 $?v_j,v_k?$ 上，則$l(i)=\text{vl(k)}?\text{weight}(?j,k?)$

數(shù)學公式

• 求所有事件的最早發(fā)生時間}：
  遞推公式： // 拓撲排序正序
  ve(k) = { 0 , k = 0 max ? { ve(j) + weight ( ? j , k ? ) } , ? v j , v k ? ∈ E ( G ) , k = 1 , 2 , … , n ? 1 \texttt{ve(k)} = \begin{cases} 0, & k = 0 \\ \max\{\texttt{ve(j)} + \texttt{weight}(\langle j, k \rangle)\}, & \langle v_j, v_k \rangle \in E(G), \; k = 1, 2, \dots, n-1 \end{cases} ve(k)={0,max{ve(j)+weight(?j,k?)},?k=0?vj?,vk??∈E(G),k=1,2,…,n?1?

• 求所有事件的最遲發(fā)生時間}：
  遞推公式：拓撲排序逆序
  vl(j) = { ve(n-1) , j = n ? 1 min ? { vl(k) ? weight ( ? j , k ? ) } , ? v j , v k ? ∈ E ( G ) , j = n ? 2 , n ? 3 , … , 0 \texttt{vl(j)} = \begin{cases} \texttt{ve(n-1)}, & j = n-1 \\ \min\{\texttt{vl(k)} - \texttt{weight}(\langle j, k \rangle)\}, & \langle v_j, v_k \rangle \in E(G), \; j = n-2, n-3, \dots, 0 \end{cases} vl(j)={ve(n-1),min{vl(k)?weight(?j,k?)},?j=n?1?vj?,vk??∈E(G),j=n?2,n?3,…,0?

偽代碼

思路
求關鍵活動的基本步驟：

• 對 AOE 網(wǎng)進行拓撲排序，若網(wǎng)中有回路，則終止算法；按拓撲次序求出各頂點事件的最早發(fā)生時間 ve
• 按拓撲序列的逆序求出各頂點事件的最遲發(fā)生時間 vl
• 根據(jù)ve和vl的值，求出各活動的最早開始時間 e(i)與最遲開始時間l(i)，若e(i) = l(i)，則 $i$ 是關鍵活動

// CPath1 - 計算事件的最早發(fā)生時間
// 初始化事件的最早發(fā)生時間
for (int i = 1; i <= n; i++) ve[i] = 0; // 最早發(fā)生時間初始化為 0// 按拓撲序計算事件的最早發(fā)生時間
for (int i = 1; i <= n; i++) {p = adjacent(Head[i]); // 獲取頂點 i 的鄰接表while (p != NULL) {k = VerAdj(p); // 獲取鄰接頂點if (ve[i] + cost(p) > ve[k]) // 更新最早發(fā)生時間ve[k] = ve[i] + cost(p);p = p->link; // 繼續(xù)訪問下一個鄰接點}
}// CPath2 - 計算事件的最遲發(fā)生時間
// 初始化事件的最遲發(fā)生時間
for (int i = 1; i <= n; i++) vl[i] = ve[n]; // 最遲發(fā)生時間初始化為最后事件的最早時間// 按拓撲逆序計算事件的最遲發(fā)生時間
for (int i = n; i >= 1; i--) {p = adjacent(Head[i]); // 獲取頂點 i 的鄰接表while (p != NULL) {k = VerAdj(p); // 獲取鄰接頂點if (vl[k] - cost(p) < vl[i]) // 更新最遲發(fā)生時間vl[i] = vl[k] - cost(p);p = p->link; // 繼續(xù)訪問下一個鄰接點}
}// CPath3 - 關鍵活動的最早開始時間和最遲開始時間
// 遍歷所有活動，計算關鍵活動
for (int i = 1; i <= n; i++) {p = adjacent(Head[i]); // 獲取頂點 i 的鄰接表while (p != NULL) {k = VerAdj(p); // 獲取鄰接頂點e = ve[i]; // 最早開始時間l = vl[k] - cost(p); // 最遲開始時間if (e == l) // 如果最早時間等于最遲時間，則為關鍵活動PRINT("<", i, ",", k, "> is Critical Activity!");p = p->link; // 繼續(xù)訪問下一個鄰接點}
}

時間復雜性

• 時間復雜性：對頂點進行拓撲排序的時間復雜性為 $O(n+e)$，以拓撲次序求ve[i]和按拓撲逆序求vl[i]}時，所需時間均為 $O(e)$。求各個活動的e[k]和l[k]的時間復雜度為 $O(e)$，整個算法的時間復雜性是 $O(n+e)$
• 定理 6.3：任意的非空 AOE 網(wǎng)至少存在一條關鍵路徑
• 推論 6.1：假設邊 $?T_i,T_j?$ 屬于 AOE 網(wǎng)，則有
  $$\text{vl[j]}?\text{ve[i]}\ge \text{Weight}(?T_i,T_j?)$$
• 且如果 $?T_i,T_j?$ 屬于某一條關鍵路徑，則有
  $$\text{vl[j]}?\text{ve[i]}=\text{Weight}(?T_i,T_j?).$$