高考申論題
108年
[資訊處理] 資料結構
第 二 題
📖 題組：
下面的無向圖（undirected graph）表示四個人的關係，如張三與李四有關係，這二人之間有邊（edge）相連，則可走訪。括弧內為人名縮寫，如張三（Chang San）的縮寫為 CS。若同時有兩個以上的人可處理，則先處理人名縮寫的字母順序較小者。 圖形結構： 張三(CS) 連接 李四(LS), 趙六(CL) 李四(LS) 連接 張三(CS), 趙六(CL), 王五(WW) 趙六(CL) 連接 張三(CS), 李四(LS), 王五(WW) 王五(WW) 連接 李四(LS), 趙六(CL)
下面的無向圖（undirected graph）表示四個人的關係，如張三與李四有關係，這二人之間有邊（edge）相連，則可走訪。括弧內為人名縮寫，如張三（Chang San）的縮寫為 CS。若同時有兩個以上的人可處理，則先處理人名縮寫的字母順序較小者。 圖形結構： 張三(CS) 連接 李四(LS), 趙六(CL) 李四(LS) 連接 張三(CS), 趙六(CL), 王五(WW) 趙六(CL) 連接 張三(CS), 李四(LS), 王五(WW) 王五(WW) 連接 李四(LS), 趙六(CL)
📝 此題為申論題，共 2 小題
小題 (二)
由張三（CS）出發，用堆疊（stack）做深度優先搜尋（depth-first search）走訪所有人，請寫出走訪順序的中文人名。（10 分）
思路引導 VIP
這題考查圖的深度優先搜尋（DFS）走訪邏輯。解題時應先將各節點的英文縮寫依照字母（字典序）排序，接著從起點出發，每次皆優先選擇相鄰、未走訪過且字母順序最小的節點進行深入走訪，直到所有節點均走訪完畢為止。
小題 (一)
由張三（CS）出發，用佇列（queue）做廣度優先搜尋（breadth-first search）走訪所有人，請寫出走訪順序的中文人名。（10 分）
思路引導 VIP
首先確認各個人名縮寫的字母字典序大小（CL < CS < LS < WW）。接著依據廣度優先搜尋（BFS）的特性，利用佇列（Queue）先進先出的原則逐步展開，當遇到多個相鄰且未拜訪的節點時，嚴格遵守字母順序較小者優先入隊的條件進行推演。