題組內容

一、佇列（queue）和堆疊（stack）是二種常用的資料結構。請回答下列問題。

⑵若要用廣度優先的方式（breadth-first search）走訪一樹狀結構（tree structure）的所有節點（node），請問佇列和堆疊，何者較適合？並說 明原因。（10 分）

詳解 (共 2 筆)

frankyanng
frankyanng
詳解 #3325953
2019/05/04
廣度優先的方式為1.從樹根開始，先將所有...
(共 138 字，隱藏中）
前往觀看
hchungw
hchungw
詳解 #6105150
2024/05/22

使用佇列進行廣度優先搜索（BFS）的原因

  1. 廣度優先的特性：

    • 廣度優先搜索需要按層次逐層走訪樹狀結構中的節點，先走訪一層的所有節點，再走訪下一層的節點。這種先進先出的訪問順序與佇列的特性完全匹配。

  2. 佇列的運作機制：

    • 當走訪到一個節點時，將其相鄰的節點（子節點）依次放入佇列中。
    • 每次從佇列的前端取出一個節點進行走訪，然後將這個節點的子節點放入佇列的末端。
    • 這樣的過程保證了每次都是先處理佇列中最早加入的節點，確保節點按照層次順序被走訪，符合廣度優先的需求。

具體操作步驟

  1. 初始化：

    • 將根節點（root node）放入佇列。

  2. 重複以下步驟直到佇列為空：

    • 從佇列的前端取出一個節點，進行處理（例如打印節點值）。
    • 將這個節點的子節點依次放入佇列的末端。
佇列（queue）因其先進先出的特性，非常適合用來實現廣度優先搜索（BFS），而堆疊（stack）則更適合深度優先搜索（DFS）。