高考申論題
109年
[資訊處理] 資料結構
第 三 題
📖 題組：
四、若我們用相鄰矩陣（Adjacency Matrix）M來表示圖一中的無向圖G = (V, E)，請考慮下面的問題：
圖一、無向圖G = (V, E)
四、若我們用相鄰矩陣（Adjacency Matrix）M來表示圖一中的無向圖G = (V, E)，請考慮下面的問題：
圖一、無向圖G = (V, E)
若將圖一無向圖G = (V, E)中的邊給予方向成為如圖二中的有向圖（Directed Graph）G’：（10分）
圖二、有向圖G’
⑴有向圖G’沒有迴圈（Cycle），是一個無迴圈有向圖（Directed Acyclic Graph, DAG），所以存在節點的拓樸排序（Topological Sort），請對G’給出一個拓樸排序（Topological Sort）。
⑵請給一個方法來判斷一個有向圖是否沒有迴圈。
圖二、有向圖G’
⑴有向圖G’沒有迴圈（Cycle），是一個無迴圈有向圖（Directed Acyclic Graph, DAG），所以存在節點的拓樸排序（Topological Sort），請對G’給出一個拓樸排序（Topological Sort）。
⑵請給一個方法來判斷一個有向圖是否沒有迴圈。
📝 此題為申論題
思路引導 VIP
本題考查有向無環圖（DAG）的拓樸排序及迴圈判斷方法。第一小題可利用計算各節點的入分枝度（In-degree），每次挑選入分枝度為 0 的節點輸出並移除其向外的邊，逐步求得拓樸排序；第二小題可順著第一小題的邏輯，說明若拓樸排序無法輸出所有節點即代表有迴圈，或是說明利用深度優先搜尋（DFS）檢查是否產生「後向邊（Back Edge）」。
🤖
AI 詳解
AI 專屬家教
【解題關鍵】拓樸排序的核心在於每次選擇入分枝度（In-degree）為 0 的節點，而判斷迴圈可利用拓樸排序的節點計數或深度優先搜尋（DFS）的後向邊檢測。 【解答】 ⑴ 拓樸排序（Topological Sort）
▼ 還有更多解析內容
拓樸排序與迴圈偵測
💡 利用入分枝度或 DFS 走訪來對 DAG 排序並判別圖形是否循環
🔗 Kahn's Algorithm 拓樸排序執行流程
- 1 計算入分枝度 — 統計圖中每個節點被指入的邊數。
- 2 佇列初始化 — 將所有入分枝度為 0 的節點放入佇列。
- 3 輸出與更新 — 取出節點輸出，並將其指向的鄰居入分枝度減 1。
- 4 循環處理 — 若鄰居度數變為 0 則入隊，重複直至佇列為空。
- 5 終局判定 — 比較輸出節點數與總數，不相等則代表有迴圈。
↓
↓
↓
↓
🔄 延伸學習：此演算法可應用於編譯程式碼的相依性檢查或專案時程安排。
