對一有n 個節點的圖形G 執行深度優先式搜尋(Depth First Search)，下列敘述那些為真？

電腦軟體設計共同科目 · 乙級 · Q251

當G 用相鄰矩陣(Adjacency Matrix)表示時，其時間複雜度為O(n)

當G 用相鄰串列表示時，其時間複雜度為O(e)，e為圖形的邊之個數

搜尋過程中需用到堆疊

搜尋過程中需用到佇列

3 / 5

本題為複選題，要求考生同時區分圖形表示法對時間複雜度的影響，並精確辨別演算法所對應的資料結構，需全面掌握核心概念才能判定所有選項的正確性。

② 當G 用相鄰串列表示時，其時間複雜度為O(e)，e為圖形的邊之個數:使用相鄰串列表示圖形時，DFS 僅需訪問每個節點及其相鄰邊，時間複雜度為 O(n+e)，當只考慮邊的遍歷時可簡述為 O(e)，其中 e 為邊數。
③ 搜尋過程中需用到堆疊:DFS 的核心機制是後進先出(LIFO)，透過遞迴呼叫堆疊或顯式堆疊(Stack) 來追蹤待探索的節點，確保沿著單一路徑深入探索。

① 當G 用相鄰矩陣(Adjacency Matrix)表示時，其時間複雜度為O(n):使用相鄰矩陣表示圖形時，DFS 需遍歷整個 n×n 矩陣來查找相鄰節點，其時間複雜度應為 O(n²) 而非 O(n)。
④ 搜尋過程中需用到佇列:佇列(Queue) 是廣度優先搜尋(BFS) 所使用的資料結構，採用先進先出(FIFO)原則逐層擴展，而非 DFS 的運作方式。

"DFS 與 BFS 是圖論搜尋的兩大核心演算法，常考陷阱在於混淆兩者的時間複雜度與所需資料結構。切記：DFS 用堆疊（深入探索），BFS 用佇列（逐層擴展）；相鄰矩陣的時間複雜度為 O(n²)，相鄰串列為 O(n+e)，兩者差異在於查找相鄰節點的效率。"

①當G 用相鄰矩陣(Adjacency Matrix)表示時，其時間複雜度為O(n)0%

②當G 用相鄰串列表示時，其時間複雜度為O(e)，e為圖形的邊之個數0%

③搜尋過程中需用到堆疊0%

④搜尋過程中需用到佇列0%

此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！