地特三等申論題
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）出發，用佇列（queue）做廣度優先搜尋（breadth-first search）走訪所有人，請寫出走訪順序的中文人名。（10 分）
思路引導 VIP
首先確認廣度優先搜尋 (BFS) 需使用佇列 (Queue) 的先進先出特性來實作。遇到多個相鄰節點時，務必先比較人名縮寫的字母順序（CL < CS < LS < WW），字母小者優先進入佇列，即可準確推導出走訪順序。
小題 (二)
由張三（CS）出發，用堆疊（stack）做深度優先搜尋（depth-first search）走訪所有人，請寫出走訪順序的中文人名。（10 分）
思路引導 VIP
看到這題，首先釐清各人名縮寫的字母順序（CL < CS < LS < WW），以及圖中各節點的相鄰關係。接著依據深度優先搜尋（DFS）「一路深入，無路可走再回溯」的特性，從起點出發，每次優先將未訪問且字母較大的鄰居先推入堆疊（或遞迴時優先選擇字母較小的鄰居深入），即可推導出正確走訪順序。