高考申論題
112年
[資訊處理] 資料結構
第 四 題
針對如下的有向圖（節點為走訪對象，連線上的數字為走訪的 cost），依如下 BFS（配合 queue）與 DFS（配合 stack）演算法，進行所有節點的走訪，多個節點可以走訪時，以連線上 cost 較低者優先，結果請以迴圈內部的顯示要求，依下表形式填入（stack 垂直表示，開口在上方，queue 水平表示，出口在左，入口在右）。註：假設節點 S 為起始點。（24 分）
[圖示及演算法虛擬碼請參考原圖]
📝 此題為申論題
思路引導 VIP
本題測驗圖形走訪演算法(BFS與DFS)的底層資料結構操作。解題關鍵在於：BFS利用Queue(先進先出)，依連線cost由低至高入列；DFS利用Stack(後進先出)並配合「反向推入」(cost高者先推入)，以確保cost低者在Stack頂端優先被取出。此外，需注意追蹤 processSet(已走訪集合) 以避免走訪重複節點。
🤖
AI 詳解
AI 專屬家教
【解題關鍵】BFS 利用 Queue（先進先出）並依 cost 由低至高入列；DFS 利用 Stack（後進先出）並依 cost 由高至低推入堆疊，以確保 pop 時低 cost 優先。 【解答】 1. BFS 演算法執行狀態表
▼ 還有更多解析內容