樹規定每個節點只有一個父節點；拿掉這個限制，就得到圖。代價是尋訪需要 visited[] 陣列防止繞圈，收穫是最短路徑、最小生成樹與專案排程這些真實世界的問題全都有了乾淨的解法。
第 6 章的編排非常規律 —— 先給兩個尋訪工具，再拿它們解四類問題：
留意一條貫串全章的線索：第 5 章的 union-find 在 6.3 節的 Kruskal 演算法再度登場，正如第 5 章結尾所預告的。
「正如 Euler 一樣，你很快地就會發現 Koenigsberg 的人們不可能經過每一橋樑恰好一次而又回到原來的出發點。Euler 以圖形來解決這個問題，其中各地區為頂點，橋樑為邊。他的解法不但巧妙，而且可應用在所有圖形上面。」
Euler 的定理：「Euler 定義一個頂點的分支度為附著在其上的邊數。而後他證明了若且唯若每一個頂點的度數為偶數，則存在一種走法從任一頂點開始，經過每一橋樑恰好一次，並回到原出發點。這種走法就稱為尤拉走法（Eulerian walk）。在 Koenigsberg 橋樑問題中找不到此種走法，因所有頂點的度數為奇數。」
「從這第一個應用以後，圖形理論廣泛地應用在各方面，包括電路分析，找出最短路徑，專案規劃，以及化學成分的鑑別等。事實上，圖形理論可說是在所有數學領域中應用最廣的一個。」
圖形 $G$ 包含兩個集合：一個是由頂點（vertices）所形成的有限的非空集合，另一個是由邊（edges）所形成的有限的非空集合。分別以 $V(G)$ 和 $E(G)$ 代表圖形 $G$ 中的頂點和邊之集合。或者，可寫成 $G=(V,E)$ 來代表一個圖形。
表示任一邊的兩個頂點是沒有方向性的。頂點序對 $(v_0,v_1)$ 和 $(v_1,v_0)$ 代表同一邊。寫成小括號。
每一邊以有方向性的兩個頂點表示。序對 $\langle v_0,v_1\rangle$ 代表尾（tail）是 $v_0$，頭（head）是 $v_1$。所以 $\langle v_0,v_1\rangle$ 和 $\langle v_1,v_0\rangle$ 代表兩個不同的邊。寫成角括號。
是具有最多邊數的圖形。
| 類型 | $n$ 個頂點時最大的邊數 |
|---|---|
| 無向圖形 | $\dfrac{n(n-1)}{2}$ |
| 有向圖形 | $n(n-1)$ |
| 名詞 | 定義 |
|---|---|
| 相鄰 adjacent | 若 $(v_0,v_1)$ 是無向圖形中的一個邊，則頂點 $v_0$ 和 $v_1$ 為相鄰的 |
| 附著於 incident on | 邊 $(v_0,v_1)$ 附著於頂點 $v_0$ 和 $v_1$ |
| 相鄰至 / 相鄰自 | 有向邊 $\langle v_0,v_1\rangle$：頂點 $v_0$ 相鄰至 $v_1$，頂點 $v_1$ 相鄰自 $v_0$ |
| 子圖 subgraph | $G'$ 是 $G$ 的子圖，若 $V(G') \subseteq V(G)$ 且 $E(G') \subseteq E(G)$ |
| 路徑 path | 從 $v_p$ 到 $v_q$ 的一連串頂點，其中相鄰兩者間都有邊。路徑的長度等於其上所有的邊數 |
| 簡單路徑 simple path | 除了第一個節點與最後一個節點外的所有節點都不相同的路徑 |
| 環路 cycle | 一個簡單路徑，其中第一個與最後一個節點相同 |
| 連通 connected | 無向圖形 $G$ 中，如果每一對不同的頂點 $v_i$、$v_j$ 之間都存在路徑 |
| 連通元件 connected component | 無向圖形中最大的連通子圖 |
| 樹 tree | 一種連通且沒有循環的圖形 |
| 強連通 strongly connected | 有向圖形中每一對頂點 $(v_i,v_j)$ 之間雙向都有路徑 |
| 度數 degree | 附著於該頂點的邊數。有向圖形另有入度數（in-degree）與出度數（out-degree） |
在具有 $n$ 個頂點和 $e$ 個邊的圖形 $G$ 中，如果 $d_i$ 是頂點 $i$ 的度數，則邊的總數為：
「在本章往後的各部份中，我們將以有向圖形（digraph）代表有方向性的圖形。當我們使用圖形一詞，它代表無方向性的圖形。」
structure Graph is
objects: a nonempty set of vertices and a set of undirected edges,
where each edge is a pair of vertices.
functions:
for all graph in Graph, v, v1, and v2 in Vertices
Graph Create() ::= return an empty graph.
Graph InsertVertex(graph, v) ::= return a graph with v inserted.
v has no incident edges.
Graph InsertEdge(graph,v1,v2) ::= return a graph with a new edge
between v1 and v2.
Graph DeleteVertex(graph, v) ::= return a graph in which v and all
edges incident to it are removed.
Graph DeleteEdge(graph,v1,v2) ::= return a graph in which the edge
(v1, v2) is removed. Leave the
incident nodes in the graph.
Boolean IsEmpty(graph) ::= if (graph == empty graph) return
TRUE else return FALSE.
List Adjacent(graph, v) ::= return a list of all vertices that
are adjacent to v.
end Graph結構 6.1：Graph 抽象資料型態
「回答這些問題的所有演算法至少需要 $O(n^2)$ 時間，因為我們必須檢查矩陣中的 $n^2 - n$ 項（對角線上的 $n$ 項等於 0，可排除）；對於無向圖形而言，因為矩陣是對稱的，所需檢查的項目只有一半來決定圖形中的邊數。」
「對於稀疏圖形（sparse graph，亦即具有少量邊數的圖形），相鄰矩陣中大多數的項目為 0，我們想要減少檢查相鄰矩陣中 $O(n^2)$ 個位置所需的負擔。事實上，我們希望前述問題可以在較少的時間內獲得答案，如 $O(e+n)$ 時間，其中 $e$ 是圖形 $G$ 中的邊數，且 $e \ll n^2/2$。因此，我們必須以相鄰串列（循序式或鏈結式）表示法來取代相鄰矩陣表示法。」
「在這個表法中，我們以 $n$ 個鏈結串列取代相鄰矩陣中的 $n$ 個列，圖形 $G$ 中的每一個頂點各有一個串列。此串列的節點構造至少包含一個頂點欄位和一個鏈結欄位。對任一串列 $i$，串列中的節點包含與頂點 $i$ 相鄰的頂點。」
在具有 $n$ 個頂點、$e$ 個邊的無向圖形情況下，這種表示法需要 $n$ 個標頭節點，以及 $2e$ 個串列節點。每一串列節點有兩個欄位。
「通常，也可以將串列中的節點以循序方式安排，以減少使用指標。在這種情況下，可以使用陣列 node[]。node[i] 存放頂點 $i$，$0 \le i \lt n$，的串列之起始位置，且 node[n] 設定為 $n+2e+1$。與頂點 $i$ 相鄰的頂點則儲存在 node[i], …, node[i+1]。」
這和第 2 章 2.4 節 fast_transpose 的 starting_pos 是同一個技巧 —— 用前綴和把可變長度的串列壓進一個陣列。
| 要計算什麼 | 相鄰串列的成本 |
|---|---|
| 無向圖形任一頂點的度數 | 計算該頂點串列上的節點個數 |
| 無向圖形全部的邊數 | $O(n+e)$ |
| 有向圖形任一頂點的出度數 | 計算其相鄰串列上的節點個數 |
| 有向圖形全部的邊數 | $O(n+e)$ |
| 有向圖形任一頂點的入度數 | 比較困難 —— 需要另一組串列 |
「我們藉使用另一組串列來處理這個問題…… 此組串列稱為反轉相鄰串列（inverse adjacency lists）。就像相鄰串列一般，每一個頂點在反轉相鄰串列中各有一個串列。但是，串列中對相鄰至該串列所代表的頂點之每一個頂點分別有一個節點。」
用於有向圖形，同時支援相鄰串列與反轉相鄰串列 —— 和第 4 章 4.7 節稀疏矩陣的十字鏈結是同一個構造。
節點構造為 marked | vertex1 | vertex2 | path1 | path2。「對任一個邊，僅有一個節點表示，但此節點存在該邊所附著的兩個頂點之串列上。」—— 對「標記已處理的邊」這類運算特別有用，因為一條邊只有一個 marked 旗標。
第 1 題：完整無向圖的每條邊對應一個「從 $n$ 個頂點中取 2 個」的組合，即 $\binom{n}{2} = n(n-1)/2$。
第 3 題（握手定理）：每條邊恰好貢獻 2 給度數總和（它的兩個端點各加 1），所以 $\sum d_i = 2e$。這就是前面 $e = \frac{1}{2}\sum d_i$ 的另一種寫法。
第 4 題（作法）：用 BFS 塗色 —— 從任一未著色頂點出發塗成 0，它的所有鄰居塗成 1，再下一層塗 0……若發現某條邊的兩端同色，就不是二分圖。每個頂點入佇列一次、每條邊檢查兩次，所以是 $O(n+e)$。（不連通的圖要對每個連通元件各做一次。）
第 5 題：樹沒有環路，所以照第 6 題的判準立刻成立。直接證法：按階層的奇偶塗色 —— 奇數層塗 $V_1$、偶數層塗 $V_2$。樹的每條邊都連接相鄰兩層，故兩端必異色。
第 6 題（$\Leftarrow$ 方向的關鍵）：若有奇數長度的環路，沿環路交替塗色走一圈，回到起點時顏色會與出發時相反 —— 矛盾。反之若無奇環，BFS 塗色必定成功（任兩條到同一頂點的路徑長度同奇偶，否則它們合起來構成奇環）。
頂點 $v$ 屬於 $V(G)$，我們想要找出從頂點 $v$ 可以到達的所有 $G$ 中之頂點，也就是說，所有連通到 $v$ 的頂點。我們將探討完成這項工作的兩種方法。
| DFS 先深後廣搜尋 | BFS 先廣後深搜尋 | |
|---|---|---|
| 類似樹的 | 先序尋訪 | 階序尋訪 |
| 用的資料結構 | 堆疊（遞迴的系統堆疊） | 佇列 |
| 策略 | 「拜訪一個頂點，並在下一個未經拜訪的後代繼續搜尋」 | 「拜訪過了所有在 $v$ 相鄰串列上的頂點後，接著拜訪與 $v$ 的相鄰串列上的第一個頂點相鄰的未經拜訪的頂點」 |
#define FALSE 0
#define TRUE 1
short int visited[MAX_VERTICES];void dfs(int v)
{
/* depth first search of a graph beginning with vertex v.*/
node_pointer w;
visited[v] = TRUE;
printf("%5d",v);
for (w = graph[v]; w; w = w->link)
if (!visited[w->vertex])
dfs(w->vertex);
}程式 6.1：先深後廣搜尋
以圖 6.19(a) 的圖形 $G$ 進行先深後廣搜尋。如果從頂點 $v_0$ 開始搜尋，則 $G$ 中的頂點以下列順序被拜訪：
「我們可以驗証 dfs(v0) 拜訪了所有連通到 $v_0$ 的頂點。這表示，所有拜訪過的頂點以及 $G$ 中附著於這些頂點的所有邊，可以形成 $G$ 的一個連通元件。」
| 圖形表示法 | 時間 | 理由 |
|---|---|---|
| 相鄰串列 | $O(e)$ | 「dfs 對相鄰串列中的各個節點至多檢查一次」 |
| 相鄰矩陣 | $O(n^2)$ | 「找出所有相鄰到 $v$ 的頂點需時 $O(n)$ 時間。因為我們最多要拜訪 $n$ 個頂點」 |
typedef struct queue *queue_pointer;
typedef struct queue {
int vertex;
queue_pointer link;
};
void addq(queue_pointer *, queue_pointer *, int);
int deleteq(queue_pointer *);「要實作先廣後深搜尋，採用如第 4 章所說明的動態鏈結佇列。第 4 章的 addq 和 deleteq 函數（程式 4.8 和 4.9）將可以正確地工作，只要將程式中的 element 的型態改為 int 即可。」
void bfs(int v)
{
/* breadth first traversal of a graph, starting with node v
the global array visited is initialized to 0, the queue
operations are similar to those described in Chapter 4. */
node_pointer w;
queue_pointer front,rear;
front = rear = NULL; /* initialize queue */
printf("%5d",v);
visited[v] = TRUE;
addq(&front, &rear, v);
while (front) {
v = deleteq(&front);
for (w = graph[v]; w; w = w->link)
if (!visited[w->vertex]) {
printf("%5d", w->vertex);
addq(&front,&rear,w->vertex);
visited[w->vertex] = TRUE;
}
}
}程式 6.2：圖形的先廣後深搜尋
「因為每一頂點都被放入佇列中一次，while 迴圈最多會執行 $n$ 次。對相鄰串列表示法而言，此迴圈的全部成本為 $d_0 + \cdots + d_{n-1} = O(e)$，其中 $d_i = \text{degree}(v_i)$。對相鄰矩陣表示法而言，每拜訪一個頂點 while 迴圈需要 $O(n)$ 時間。因此，全部的時間為 $O(n^2)$。正如 dfs 一般，所有已拜訪的頂點與所有附著於其上的邊可形成圖形 $G$ 的連通元件。」
注意 bfs 在 加入佇列的同時就設 visited[w->vertex] = TRUE，而不是等到取出佇列才標記。若延後標記，同一個頂點可能被多個鄰居重複加入佇列，佇列長度會膨脹、輸出也會重複。這是 BFS 最常見的實作錯誤。
void connected(void)
{
/* determine the connected components of a graph */
int i;
for (i = 0; i < n; i++)
if(!visited[i]) {
dfs(i);
printf("\n");
}
}程式 6.3：連通元件 ——「雖然我們選用 dfs，也可以改用 bfs 而不影響其時間複雜度。」
「如果 $G$ 以相鄰串列表示，則 dfs 所需的全部時間為 $O(e)$。因 for 迴圈需要 $O(n)$ 時間，要產生所有的連通元件所需的時間為 $O(n+e)$。如果 $G$ 以相鄰矩陣表示，則決定連通元件所需的時間為 $O(n^2)$。」
判斷「是否連通」更簡單：「這個運算的實作只要呼叫 dfs(0) 或 bfs(0) 並判斷是否有未經拜訪的頂點即可。例如，圖 6.5 上的圖形 $G_4$ 在呼叫 dfs(0) 執行結束時，未拜訪到的頂點有 4、5、6 和 7。所以，可獲得結論，$G_4$ 不是連通的圖形。」
「當圖形 $G$ 是連通的，從任一頂點開始的先深或先廣搜尋可以拜訪 $G$ 中所有的頂點。這種搜尋會將 $G$ 的邊分成兩組：$T$（代表樹邊）和 $N$（代表非樹邊）。$T$ 是在搜尋期間利用到的或經過的一組邊，$N$ 則是剩下的邊。」
定義：生成樹（spanning tree）是包含 $G$ 中的邊以及 $G$ 全部的頂點之任一樹狀結構。
第二個特性：「一個生成樹是一個圖形 $G$ 的最小子圖（minimal subgraph） $G'$，使得 $V(G')=V(G)$ 且 $G'$ 是連通的。…… 對任一具 $n$ 個頂點的連通圖形，至少有 $n-1$ 個邊，且所有具有 $n-1$ 個邊的連通圖形都是樹狀結構。所以，我們獲得一個結論，生成樹有 $n-1$ 個邊。」
「要找出所有的樹邊，只要在 dfs 或 bfs 的 if 子句中加入一個指令，將邊 $(v,w)$ 插入邊的鏈結串列中。」—— 一行就夠了。用 dfs 得到的稱為先深生成樹，用 bfs 得到的稱為先廣生成樹。
「在通訊網路的設計上，找出最小子圖是常見的應用。假設圖形 $G$ 中的頂點代表城市，邊代表城市之間的網路線。要連接 $n$ 個城市所需要的最少網路線是 $n-1$。找出圖形 $G$ 的生成樹可以提供所有可能的連接方法。但是，我們知道在不同的城市之間建立網路線的成本幾乎都是不同的。所以，在實際的應用上，對每一個邊都指定了一個權數。…… 有了這種已加權的圖形，我們就可以選擇一個代表具有最小總成本或最小總長度的生成樹。」—— 這就是 6.3 節的主題。
「到目前為止，我們所製作的運算都是先深和先廣搜尋的簡易擴充。我們想要製作的下一個運算則較複雜，且需要先說明一些專用術語。首先，我們假設圖形 $G$ 為一個沒有方向的連通圖形。」
連接點是圖形 $G$ 的一個頂點 $v$，如果將 $v$ 以及所有附著於 $v$ 的邊刪除，將產生一個圖形 $G'$，且 $G'$ 至少有兩個連通元件。例如，圖 6.22 中的連通圖形有四個連接點，即頂點 1、3、5 和 7。
| 名稱 | 意義 |
|---|---|
dfn[u] | 頂點 $u$ 在先深搜尋中被拜訪的序號（depth first number） |
low[u] | 從 $u$ 出發，沿著先深生成樹往下走任意步、最多再走一條回邊，所能到達的最小 dfn |
「所以，我們可以說 $u$ 是一個連接點，若且唯若：
課本以圖 6.24 逐一驗證：「頂點 1 為連接點，因它有一個子節點 0，$\texttt{low}(0)=4 \ge \texttt{dfn}(1)=3$。頂點 7 也是連接點，因 $\texttt{low}(8)=9 \ge \texttt{dfn}(7)=7$，頂點 5 也是，因 $\texttt{low}(6)=5 \ge 5$。最後，請留意根節點，頂點 3，也是連接點，因它有一個以上的子節點。」
| Vertex | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| dfn | 4 | 3 | 2 | 0 | 1 | 5 | 6 | 7 | 9 | 8 |
| low | 4 | 3 | 0 | 0 | 0 | 5 | 5 | 7 | 9 | 8 |
圖 6.24：root = 3 的 dfs 生成樹的 dfn 和 low 值
#define MIN2(x,y) ((x) < (y) ? (x) : (y))
short int dfn[MAX_VERTICES];
short int low[MAX_VERTICES];
int num;
void init(void)
{
int i;
for (i = 0; i < n; i++) {
visited[i] = FALSE;
dfn[i] = low[i] = -1;
}
num = 0;
}程式 6.5：dfn 和 low 之初值設定
「函數 bicon 假設連通圖形至少有兩個頂點。技術上而言，一個圖形只有一個頂點而沒有邊時是二連通的，但是，我們製作的程式並未處理這個特例。bicon 的複雜度為 $O(n+e)$。其正確性的証明則留作習題。」
「在 dfnlow 中加入一些程式碼即可將連通圖形的邊分割成連通元件。我們已知 low[w] 在函數呼叫 dfnlow(w,u) 後已被計算並傳回。如果 low[w] >= dfn[u]，則我們可找出一個新的二連通元件。如果在找到二連通元件的邊時即將它們保存在堆疊中，我們即可將一個二連通元件的所有邊都印出。」
dfs 應用在 connected 時，應如何修改以產生最近尋訪的所有頂點之序列。dfs 應用在連通圖形時，$T$ 中的邊可形成樹狀結構。bfs 應用在連通圖形時，$T$ 中的邊可形成樹狀結構。bicon 當作出發點。）第 5 題（橋 —— 和連接點的判準只差一個等號）：
對照連接點的判準是 $\texttt{low}[w] \boldsymbol{\ge} \texttt{dfn}[u]$。差別在等號：
所以只要把 bicon 裡的 >= 改成 >，並輸出那條樹邊即可。時間仍是 $O(n+e)$。
第 3、4 題的共同論證：$T$ 中恰有 $n-1$ 條邊（每個非起點頂點在第一次被拜訪時貢獻一條），且 $T$ 連通（每個頂點都經由 $T$ 的邊從起點可達）。$n$ 個頂點 + $n-1$ 條邊 + 連通 ⇒ 樹。
對有加權的無向圖形的生成樹成本中各邊的成本（權數）之和。最小成本生成樹（minimum cost spanning tree）是具有最少的成本之生成樹。有三種不同的演算法可用來找出連通無向圖形最小成本生成樹：Kruskal、Prim 和 Sollin 演算法。
「這三種方法均採用稱為貪婪法則的演算法設計策略。在貪婪法則中，我們逐步建立最佳解法。在每一步驟中，我們要（利用一些條件）找出現階段最佳的決策。因為這個決策以後不可改變，我們必須確定此決策能產生可行的辦法。」
對生成樹而言，我們使用的條件是最小成本。我們的解答必須符合下列限制：
「Kruskal 演算法每次在 $T$ 中加入一個邊以形成最小成本生成樹 $T$。這個演算法根據各邊的成本以遞增的方式選取要加入 $T$ 的邊。一個邊若與 $T$ 原來已有的邊不會形成環路，即可加入 $T$ 中。因為 $G$ 是連通的且有 $n \gt 0$ 個頂點，所以恰有 $n-1$ 個邊會被選入 $T$ 中。」
T = {};
while (T contains less than n-1 edges && E is not empty) {
choose a least cost edge (v,w) from E;
delete (v,w) from E;
if ((v,w) does not create a cycle in T)
add (v,w) to T;
else
discard (v,w);
}
if (T contains fewer than n-1 edges)
printf("No spanning tree\n");程式 6.7：Kruskal 演算法
| 邊 | 加權 | 結果 |
|---|---|---|
| ---- | --- | 起始 |
| (0,5) | 10 | 加入樹中 |
| (2,3) | 12 | 加入 |
| (1,6) | 14 | 加入 |
| (1,2) | 16 | 加入 |
| (3,6) | 18 | 刪除（會形成環路） |
| (3,4) | 22 | 加入 |
| (4,6) | 24 | 刪除 |
| (4,5) | 25 | 加入 |
| (0,1) | 28 | 不考慮（已有 $n-1$ 個邊） |
圖 6.26：將 Kruskal 演算法應用到圖 6.25(a) 的摘要 —— 此生成樹的成本為 99
| 子運算 | 用什麼做 | 成本 |
|---|---|---|
| 選最小成本邊 | 最小累堆（第 5 章 5.6 節） | 建堆 $O(e)$，每次取出 $O(\log e)$ |
| 檢查是否形成環路 | union-find（第 5 章 5.10 節） | 每次約 $O(\alpha)$ |
這正是第 5 章結尾預告的「在第 6 章，我們將會看到 union_find 演算法的另一個應用」。兩個頂點若 find 出同一個根，代表它們已經連通，這條邊就會形成環路。總複雜度 $O(e\log e)$。
「令 $U$ 是最小成本的生成樹。$T$ 和 $U$ 兩者都恰有 $n-1$ 個邊。若 $T = U$，則 $T$ 為最小成本的，我們就不須証明了。所以假設 $T \ne U$。」
「我們必須藉著將 $U$ 轉換成 $T$ 來証明 $T$ 和 $U$ 具有相同的成本。這個轉換以 $k$ 個步驟完成。在每一步驟中，在 $T$ 而不在 $U$ 中的邊數減 1。而且，轉換的結果 $U$ 的成本不會改變。」每一步：取 $e$ 為在 $T$ 而不在 $U$ 之最小成本的邊；把 $e$ 加入 $U$ 會產生一個環路；令 $f$ 為在此環路而不在 $T$ 中的任一邊。則 $V = U + \{e\} - \{f\}$ 仍是生成樹，且成本不變 —— 因為若 $\text{cost}(e) \lt \text{cost}(f)$ 則 $V$ 比 $U$ 便宜（矛盾），若 $\text{cost}(e) \gt \text{cost}(f)$ 則 Kruskal 會先選 $f$（也矛盾）。□
「就像 Kruskal 演算法一般，Prim 演算法以一次加入一邊的方式建立最小成本生成樹。但是，在此演算法的每一步驟中，所選擇的邊之集合形成一樹狀結構。相反地，在 Kruskal 演算法的每一步驟中所選擇的邊之集合形成樹林。」
「在每一步驟中選擇恰有一個頂點 $u$ 或 $v$ 在 $T$ 中的邊 $(u,v)$。」
T = {};
TV = {0}; /* start with vertex 0 and no edges */
while (T contains fewer than n-1 edges) {
let (u, v) be a least cost edge such that u in TV and
v not in TV;
if (there is no such edge)
break;
add v to TV;
add (u, v) to T;
}
if (T contains fewer than n-1 edges)
printf("No spanning tree\n");程式 6.8：Prim 演算法 —— $T$ 為樹的邊之集合，$TV$ 為樹的頂點之集合
「要實作 Prim 演算法，假設每一頂點 $v$ 是不在 $TV$ 中且有一對應的頂點 near(v)，使得 $\texttt{near}(v) \in TV$ 且 $\text{cost}(\texttt{near}(v), v)$ 是所有可能的 near(v) 中最小的。（假設 $\text{cost}(v,w)=\infty$，若 $(v,w) \notin E$。）在每一步驟中，選擇使得 $\text{cost}(\texttt{near}(v), v)$ 為最小的 $v$ 且 $v \notin TV$。使用這種方法，Prim 演算法可以在 $O(n^2)$ 內實作，其中 $n$ 為 $G$ 中的頂點數。還有較快的實作，其中之一是應用費氏累堆（Fibonacci heap），將在第 9 章說明。」
「不同於 Kruskal 和 Prim 演算法，Sollin 演算法在每一步驟中選擇數個可加入 $T$ 的邊。在每一步驟開始時，所選擇的邊以及圖形的所有 $n$ 個頂點形成一個生成樹林。」—— 每一棵樹各自選出「連到樹外的最小成本邊」，然後同時合併。因為每一輪樹的數目至少減半，所以只需 $O(\log n)$ 輪。
第 1 題的複雜度：建最小累堆 $O(e)$；最多取出 $e$ 條邊，每次 $O(\log e)$；每條邊做兩次 find 與最多一次 union，共 $O(e\,\alpha(e,n))$。總計 $O(e\log e)$，因為排序項是主導項。注意 $e \le n^2$，所以 $\log e = O(\log n)$，也可寫成 $O(e\log n)$。
三種演算法的複雜度對照：
| 演算法 | 複雜度 | 適合 |
|---|---|---|
| Kruskal | $O(e\log e)$ | 稀疏圖（$e$ 小） |
| Prim（陣列） | $O(n^2)$ | 稠密圖（$e \approx n^2$） |
| Prim（費氏累堆） | $O(e + n\log n)$ | 兩者皆宜（第 9 章） |
| Sollin | $O(e\log n)$ | 易於平行化 |
第 3 題：不唯一。最簡單的反例是三個頂點的三角形，三條邊成本都是 1 —— 任選兩條都是成本 2 的最小生成樹，共 3 種。反之，若所有邊的成本兩兩不同，則最小成本生成樹是唯一的（用上面的交換論證可證：任何兩棵最小生成樹之間的交換步驟都會要求 $\text{cost}(e)=\text{cost}(f)$，與「成本兩兩不同」矛盾）。
「定義一個路徑的長度為該路徑上每一個邊的權之加總，而不是該路徑的邊數。路徑開始的頂點稱為起點，最後的一個頂點稱為目的。因為有些道路可能是單行道，圖形是有方向性的。除非有特別說明，我們亦假設權數均為正的。」
「以圖 6.29(a) 的圖形為例。如果 $v_0$ 為起點，則從 $v_0$ 到 $v_1$ 的最短路徑為 $v_0, v_2, v_3, v_1$。此路徑的長度為 $10+15+20=45$。雖然在此路徑中有三個邊，它比長度為 50 的路徑 $v_0, v_1$ 還短。」
令 $S$ 代表包括 $v_0$ 在內的頂點集合，其最短路徑已經找出。對於不在 $S$ 中的 $w$，令 distance[w] 為從 $v_0$ 開始，經由 $S$ 中的頂點而到達 $w$ 的路徑之長度。
(1) 若下一個最短路徑到達 $u$ 頂點，則由 $v_0$ 到 $u$ 的路徑只會經過 $S$ 中的頂點。
證明：「我們必須證明在 $v_0$ 到 $u$ 的最短路徑的中間頂點已經在 $S$ 中。假設有一頂點 $w$ 在此路徑上但不在 $S$ 中。則由 $v_0$ 到 $u$ 的路徑也包含了一條從 $v_0$ 到 $w$ 的路徑，其路徑長度小於由 $v_0$ 到 $u$ 的路徑之長度。因為我們假設最短路徑是根據長度由小而大來產生，我們必定已經找到從 $v_0$ 到 $w$ 的路徑。這顯然是矛盾的。所以，不可能有不存在 $S$ 內的中間節點。」
(2) 從不在 $S$ 的各頂點中選擇一個頂點 $u$，使得它具有最小的距離 distance。
#define MAX_VERTICES 6 /*maximum number of vertices */
int cost[][MAX_VERTICES] =
{{ 0, 50, 10, 1000, 45, 1000},
{1000, 0, 15, 1000, 10, 1000},
{ 20, 1000, 0, 15, 1000, 1000},
{1000, 20, 1000, 0, 35, 1000},
{1000, 1000, 30, 1000, 0, 1000},
{1000, 1000, 1000, 3, 1000, 0}};
int distance[MAX_VERTICES];
short int found[MAX_VERTICES];
int n = MAX_VERTICES;程式 6.9：最短路徑演算法之宣告
「我們使用 1000 代表不存在的邊。這個數值必須滿足：
distance[u] + cost[u][w] 產生溢位。「限制 (2) 使得 INT_MAX（定義於 <limits.h>）對不存在的邊而言是不好的選擇。」—— 這是實作最短路徑時最常見的 bug：用 INT_MAX 當 $\infty$，然後 INT_MAX + cost 溢位變成負數，於是演算法認為找到了「超短」的路徑。
void shortestpath(int v, int cost[][MAX_VERTICES],
int distance[], int n, short int found[])
{
/* distance[i] represents the shortest path from vertex v
to i, found[i] holds a 0 if the shortest path from vertex i
has not been found and a 1 if it has, cost is the
adjacency matrix */
int i,u,w;
for (i = 0; i < n; i++) {
found[i] = FALSE;
distance[i] = cost[v][i];
}
found[v] = TRUE;
distance[v] = 0;
for (i = 0; i < n-2; i++) {
u = choose(distance,n,found);
found[u] = TRUE;
for (w = 0; w < n; w++)
if (!found[w])
if (distance[u] + cost[u][w] < distance[w])
distance[w] = distance[u] + cost[u][w];
}
}程式 6.10：單一起點最短路徑（Dijkstra 演算法）
「具有 $n$ 個頂點的圖形本演算法需時 $O(n^2)$。要明白它，則注意第一個 for 迴圈需要 $O(n)$ 時間。第二個 for 迴圈執行 $n-2$ 次。每次執行此迴圈需要 $O(n)$ 時間來選擇下一個頂點並更新 dist。所以此迴圈要 $O(n^2)$ 時間。」
「任何最短路徑演算法必須檢查圖形中每一邊至少一次，因任一邊有可能出現最短路徑內。所以，對這樣的演算法最小的可能時間為 $O(e)$。因我們以成本相鄰矩陣表示圖形，要判斷 $G$ 中的每一邊需要 $O(n^2)$。所以，任何使用這種表示法的最短路徑演算法的時間複雜度為 $O(n^2)$。習題中探討數個加快速度的演算法，但漸進時間的複雜度仍為 $O(n^2)$。對於只有少數邊的圖形而言，利用費氏累堆和相鄰串列表示法，對於單一起點到所有其他目的地的問題之貪婪演算法可以產生更有效率的實作。將在第 9 章討論。」
兩個規則之一，即可產生 $A^k$：
「函數 allcosts（程式 6.12）計算 $A^{n-1}[i][j]$。計算可以在陣列 distance 中就地完成…… 此計算可以就地執行的原因是 $A^k[i][k] = A^{k-1}[i][k]$ 且 $A^k[k][j] = A^{k-1}[k][j]$，所以就地計算不會影響最後結果。」
直觀理由：第 $k$ 輪用到的第 $k$ 列和第 $k$ 行，在第 $k$ 輪中不會改變（因為經過 $k$ 再回到 $k$ 沒有意義，權數為正）。所以只需要一個 $n \times n$ 陣列，不需要 $n$ 份。
「本演算法特別容易分析，因迴圈與距離矩陣中的資料無關。allcosts 所需全部時間為 $O(n^3)$。習題中將討論將函數擴充為必須產生具有這些長度的路徑 $\langle i,j \rangle$。我們亦可以利用內層 for 迴圈僅在 distance[i][k] 和 distance[k][j] 不為 $\infty$ 才會執行的事實來使演算法加快。」
呼叫 $n$ 次 shortestpath 也是 $O(n \cdot n^2) = O(n^3)$ —— 漸進上相同。但 allcosts 的程式碼短得多、常數因子小，而且能處理負權數的邊（只要沒有負環路）—— 這是 Dijkstra 做不到的（見習題 4）。
「假設有一個有向圖形 $G$，其上的邊沒有加權。對所有的 $i$ 和 $j$ 值，我們想要找出從 $i$ 到 $j$ 是否有一路徑存在。有兩種值得探討的狀況。第一種是正的路徑長度，第二種是負的路徑長度。它們分別是圖形的遞移封包和反身封包。」
$A^+[i][j]=1$，若從 $i$ 到 $j$ 有一長度 $\gt 0$ 的路徑存在；否則 $A^+[i][j]=0$。
$A^*[i][j]=1$，若從 $i$ 到 $j$ 有一長度 $\ge 0$ 的路徑存在；否則 $A^*[i][j]=0$。
「明顯地，$A^+$ 和 $A^*$ 只有主對角線不同。因此，$A^+[i][i]=1$ 若且唯若存在一個包含頂點 $i$，長度 $\gt 1$ 的環路存在。相對地，$A^*[i][i]$ 恆為 1，因為從 $i$ 到 $i$ 永遠有一個長度為 0 的路徑存在。」
作法：「應用 allcost 可以容易地找出 $A^+$。首先修改 cost，使得 $\text{cost}[i][j]=1$ 若…」—— 把「相加取最小」換成「邏輯 or / and」即可，這就是 Warshall 演算法，同樣是 $O(n^3)$。
shortestpath 不能正確地執行之有向圖（含有權數 −2 的邊）。說明為什麼。第 3 題（本節最重要的觀念）：Dijkstra 演算法的正確性完全建立在「權數均為正」這個假設上。觀察結果 (1) 的證明用到：「由 $v_0$ 到 $u$ 的路徑也包含了一條從 $v_0$ 到 $w$ 的路徑，其路徑長度小於由 $v_0$ 到 $u$ 的路徑之長度」。
若有負權數，這句話就不成立 —— 一條較長的前綴路徑，後面接上一條負權邊之後，總長度可能反而更短。於是 Dijkstra 在把某個頂點標記為 found（即「它的最短路徑已經確定」）時可能是錯的，而且因為 found[u] = TRUE 之後就不再更新它，這個錯誤永遠不會被修正。
範例 6.5 的極端情況：課本指出「$A^1[0][2] = -\infty$，因為下列路徑的長度可設為任一很小的數值」—— 若圖中有負環路，繞環路的次數越多路徑越短，最短路徑根本不存在。
正確的作法：有負權數但無負環路時用 Bellman-Ford（$O(ne)$）或 allcosts（$O(n^3)$）。allcosts 之所以能處理負權，是因為它對每一個中繼頂點 $k$ 都重新考慮所有序對，沒有「一旦確定就不再更新」的假設。
「除了很簡單的計劃以外，我們可以將計劃分割成數個子計劃，稱為作業（activities）。當每一作業完成時，整個計畫也成功地結束。舉例而言，一個想獲得計算機科學學位的學生必須通過數種課程。在這種情況下，計劃為取得學位，而作業為個別的課程。」
「我們可證明優先順序關係是非反身性的，只要證明網路中不存在有向環路即可。不具有環路的有向圖形稱為有向無環路圖形（directed acyclic graph，dag）。」
定義：拓樸序列（topological order）是圖形中頂點的線性順序，其中任意兩個頂點 $i$、$j$，若在網路中 $i$ 是 $j$ 的前行點，則線性順序中 $i$ 也在 $j$ 之前。
「對圖 6.38(b) 的網路，有數個可行的拓樸序列，包括：」
C1,C2,C4,C5,C3,C6,C8,C7,C10,C13,C12,C14,C15,C11,C9
和
C4,C5,C2,C1,C6,C3,C8,C15,C7,C9,C10,C11,C12,C13,C14「圖 6.38(b) 中課程的拓樸序列表示可以完全符合計算機科學學位需求的一種修課過程。」
「將事件排序成為拓樸序列的演算法是很直接的。一開始，我們先列出網路中沒有前行點的一個頂點。然後從網路中刪除這個頂點以及由它出來的所有邊。重複這兩個步驟，直到所有頂點都已列出，或剩下的所有頂點均有前行點而無法將它們刪除為止。此種狀況下，網路中有環路存在，而計劃是不可行的。」
| 子運算 | 怎麼做 |
|---|---|
| (1) 決定一個頂點是否有前行點 | 「記錄每一個頂點的直接前行點之數目」（即入度數，存在標頭節點的 count 欄位） |
| (2) 刪除一個頂點及附著於其上的所有邊 | 「以網路的相鄰串列來表示它。而後，藉著將一個頂點的相鄰串列上的所有頂點之前行點計數減量」 |
「當一個頂點的計數減為 0，我們將此頂點放到一個具有零計數的頂點串列中。我們以此串列來選擇下一個頂點。」
typedef struct node *node_pointer;
typedef struct node {
int vertex;
node_pointer link;
};
typedef struct {
int count;
node_pointer link;
} hdnodes;
hdnodes graph[MAX_VERTICES];用於 topsort 的宣告 —— count 欄位包含頂點的入度數，link 為指向其相鄰串列第一個節點的指標
「我們以一個堆疊來儲放計數為零的節點串列。我們也可採用行列，但堆疊較易實作，我們以標頭節點的 count 欄位將堆疊鏈結起來，因為這個欄位在計數變成零以後就沒有作用。」—— 不需要額外的堆疊陣列，直接重用已經沒用的欄位。這和第 4 章 4.6 節「改變鏈結欄方向當堆疊」是同一個精神。
設 $d_i$ 為頂點 $i$ 的出度數。「因此迴圈每印出一個頂點即執行一次，演算法中這個部份所需的全部時間為：」
「因此，此演算法漸近計算時間為 $O(e+n)$，與問題的大小成線性關係！」
「在邊上的作業網路或稱 AOE 網路是一種與 AOV 相當接近的一種作業網路。圖形中的有向邊代表計劃中要執行的事件或作業。頂點代表一個指示某一作業完成的事件。所以，一個事件只有在所有進入它的作業都已完成時才會發生。」
簡言之：AOV 的「作業」在頂點上，AOE 的「作業」在邊上、頂點是里程碑。邊上的數字代表執行作業所需要的時間。
「因為 AOE 網路上的作業，可以同時進行，整個計劃所需要的最短時間為從起點到結束頂點的最長路徑之長度。（假設路徑的長度為在此路徑上的作業時間之加總。）臨界路徑（critical path）是具有最大長度的路徑。例如，圖 6.41(a) 的網路之臨界路徑為 $v_0, v_1, v_4, v_7, v_8$。此路徑的長度為 18。一個網路上可以有許多個臨界路徑。在圖 6.41(a) 的網路中，路徑 $v_0, v_1, v_4, v_6, v_8$ 也是一個臨界路徑。」
| 名稱 | 定義 |
|---|---|
earliest[i] | 事件 $v_i$ 可以發生的最早時間 = 從起點 $v_0$ 到 $v_i$ 的最長路徑之長度 |
latest[i] | 事件 $v_i$ 可以發生而不影響計劃期間的最晚時間 |
early(i) | 作業 $a_i$ 的最早開始時間（由該頂點出來的邊） |
late(i) | 作業 $a_i$ 可以開始而不影響計劃期間的最晚時間 |
「late(i) 和 early(i) 之間的差距是用來評估一個作業的臨界程度。它表示我們可以延緩或減慢一個作業而不會增加完成全部計劃所需的全部時間。例如，完成作業 $a_5$ 的工作時間可以再加 2 天而不會影響計劃時間。」
「顯然地，在臨界路徑上的所有作業是有決定性的，而且縮短非臨界作業所需的時間對計劃的時間不會有影響。臨界路徑之分析找出臨界作業，使我們可以集中資源以減少計劃的執行時間。臨界路徑法已經證明在評估計劃效率和找出瓶頸方面非常有用。」
| 階段 | 計算 | 順序 |
|---|---|---|
| 向前 | earliest[] | 依拓樸序列，「可以在產生拓樸序列的同時完成」 |
| 向後 | latest[] | 依拓樸序列相反的順序 |
「如果已完成向前階段並已得到頂點的拓樸序列，我們可以直接以公式 (6.4) 來計算 latest[i] 之值。以拓樸序列相反的順序來進行計算。」圖 6.42(b) 所產生的拓樸序列為 $v_0, v_3, v_5, v_2, v_1, v_4, v_7, v_6, v_8$，計算 latest[i] 值之順序為 $8, 6, 7, 4, 1, 2, 5, 3, 0$。
latest[8] = earliest[8] = 18
latest[6] = min{earliest[8] - 2} = 16
latest[7] = min{earliest[8] - 4} = 14
latest[4] = min{earliest[6] - 9; earliest[7] - 5} = 7
latest[1] = min{earliest[4] - 1} = 6
latest[2] = min{earliest[4] - 1} = 6
latest[5] = min{earliest[7] - 4} = 10
latest[3] = min{earliest[5] - 2} = 8
latest[0] = min{earliest[1] - 6; earliest[2] - 4; earliest[3] - 5} = 0「一旦算出，我們即可利用 earliest（圖 6.42）和 latest（圖 6.43）之值計算 early(i) 和 late(i) 的時間，以及每一工作的臨界程度。我們發現臨界作業為 $a_0, a_3, a_6, a_7, a_9$ 和 $a_{10}$。從網路中刪除所有的非臨界作業，可獲得圖 6.45。」
「我們以提醒讀者 topsort 僅能找出網路中的有向環路做為對作業網路的最後說明。在網路中可能還會有一些缺失，例如從開始頂點無法到達的頂點（見圖 6.46）。當我們在類似這樣的網路上進行臨界路徑分析時，將會有數個頂點的 earliest[i] = 0。所以，我們也可以利用臨界路徑分析來偵測計劃規劃中的這種錯誤。」
課本提到臨界路徑法被用於 PERT（performance evaluation and review technique）、CPM（critical path method）和 RAMPS（resource allocation and multiproject scheduling）。這是本書中少數直接對應到專案管理實務的內容。
| 主題 | 參考書目 |
|---|---|
| 圖論 | F. Harary, Graph Theory, Addison-Wesley, Reading, Mass.（課本在 6.2.4 節生成樹的討論中引用） |
INT_MAX 當 $\infty$（會溢位）。count（入度數）與零計數堆疊。AOE 臨界路徑 = 最長路徑；臨界作業 $\iff \texttt{early}(i)=\texttt{late}(i)$。| 演算法 | 相鄰串列 | 相鄰矩陣 |
|---|---|---|
dfs / bfs | $O(e)$ | $O(n^2)$ |
connected | $O(n+e)$ | $O(n^2)$ |
bicon | $O(n+e)$ | — |
| Kruskal | $O(e\log e)$ | |
| Prim | $O(n^2)$ | |
| Sollin | $O(e\log n)$ | |
shortestpath | $O(n^2)$ | |
allcosts | $O(n^3)$ | |
| 遞移封包 | $O(n^3)$ | |
topsort | $O(n+e)$ | $O(n^2)$ |
| 臨界路徑 | $O(n+e)$ | — |
INT_MAX 當 $\infty$ 會溢位。topsort 只抓環路，抓不到「不可達頂點」。用到前面的：6.2 節的 DFS/BFS 直接對應第 5 章的先序／階序尋訪；BFS 的佇列就是第 4 章程式 4.8／4.9 的鏈結佇列（只把 element 改成 int）；Kruskal 用第 5 章 5.6 節的最小累堆與 5.10 節的 union-find；相鄰串列的循序表示法用第 2 章 fast_transpose 的前綴和技巧；6.1 節的正交表示法就是第 4 章 4.7 節稀疏矩陣的十字鏈結。
接到後面的：第 9 章的費氏累堆會把 Prim 改進到 $O(e+n\log n)$、把 Dijkstra 改進到相同界限 —— 課本在 6.3 和 6.4 兩節都明白預告了這一點。