高考申論題
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）
▼ 還有更多解析內容