資料結構教科書習題解析：第 7 章 圖（Graph）完整題解與演算法實作

7.24 DFS 非遞迴實作（堆疊模擬）

void DFS_NonRec(Graph G, int v) {
    Stack S; InitStack(&S);
    Visit(v); Push(&S, v);
    while (!StackEmpty(S)) {
        int u = GetTop(S);
        int w = FirstAdjVex(G, u);
        while (w != -1 && visited[w]) w = NextAdjVex(G, u, w);
        if (w != -1) {
            Visit(w); Push(&S, w);
        } else {
            Pop(&S, &u);  // 回溯
        }
    }
}

7.31 強連通分量 (Kosaraju/Tarjan)

• Kosaraju：兩次 DFS，第一次記錄完成時間，第二次在轉置圖按時間遞減搜尋。
• Tarjan：單次 DFS，維護 dfn/low 陣列與堆疊，low[u] == dfn[u] 為強連通分量根。

7.42 關鍵路徑 CPM 實作（鄰接表）

// 拓撲排序求 ve[]
// 逆拓撲序求 vl[]
// e(ai) = ve(尾點), l(ai) = vl(頭點) - 耗時
// e==l 輸出關鍵活動

7.42 Dijkstra 鄰接表實作

void Dijkstra(Graph G, int src) {
    // dist[] 初始化 INF, dist[src]=0
    // S[] 標記已確定最短路徑
    for (i=0; i