四、針對如下的有向圖（節點為走訪對象，連線上的數字為走訪的 cost），依 如下 BFS（配合 queue）與 DFS（配合 stack）演算法，進行所有節點的走訪，多個節點可以走訪時，以連線上 cost 較低者優先，結果請以迴圈 內部的顯示要求，依下表形式填入（stack 垂直表示，開口在上方，queue 水平表示，出口在左，入口在右） 。註：假設節點 S 為起始點。（24 分）

 

 

 

廣度優先搜尋 (BFS) 使用佇列:

• 佇列:節點從後端新增,從前端移除。
• 處理集合:正在被探索的節點集合。
• 遍歷順序:節點依照被新增至佇列的順序探索,對被訪問的節點,成本較低的邊優先。

深度優先搜尋 (DFS) 使用堆疊:

• 堆疊:節點從頂端新增,從頂端移除。
• 處理集合:正在被探索的節點集合。

廣度優先搜尋 (BFS):

• 訪問節點的順序:S, A, X, B, D, C, Y, Z
• 處理集合: {C, D, X, S, A, Z, B, Y}

深度優先搜尋 (DFS):

• 訪問節點的順序:S, A, X, Y, Z, C, D, B
• 處理集合:{C, D, X, S, A, Z, B, Y}

廣度優先搜尋 (BFS) 步驟:

1. 訪問 S,佇列:S,處理集合:C, S, A, B
2. 訪問 A,佇列:A -> B -> C,處理集合:C, D, X, S, A, B
3. 訪問 X,佇列:X -> B -> D -> C,處理集合:C, D, X, S, A, B, Y
4. 訪問 B,佇列:B -> C -> D -> Y,處理集合:C, D, X, S, A, B, Y
5. 訪問 D,佇列:D -> C -> Y -> C -> D,處理集合:C, D, X, S, A, B, Y
6. 訪問 C,佇列:C -> C -> Y -> C -> D -> Y,處理集合:C, D, X, S, A, Z, B, Y
7. 訪問 Y,佇列:Y -> Y -> Z,處理集合:C, D, X, S, A, Z, B, Y
8. 訪問 Z,佇列:Z -> Z -> Y,處理集合:C, D, X, S, A, Z, B, Y

深度優先搜尋 (DFS) 步驟:

1. 訪問 S,堆疊:S,處理集合:C, S, A, B
2. 訪問 A,堆疊:A -> B -> C,處理集合:C, D, X, S, A, B
3. 訪問 X,堆疊:X -> D -> B -> C,處理集合:C, D, X, S, A, B, Y
4. 訪問 Y,堆疊:Y -> D -> B -> C,處理集合:C, D, X, S, A, Z, B, Y
5. 訪問 Z,堆疊:Z -> D -> D -> B -> C,處理集合:C, D, X, S, A, Z, B, Y
6. 訪問 C,堆疊:C -> D -> D -> B -> C,處理集合:C, D, X, S, A, Z, B, Y
7. 訪問 D,堆疊:D -> B -> D -> D -> B -> C,處理集合:C, D, X, S, A, Z, B, Y
8. 訪問 B,堆疊:B -> B -> D -> D -> B -> C,處理集合:C, D, X, S, A, Z, B, Y

AI创作