第 一 題

1. 深度優先搜尋法 (DFS)：是一種用於遍歷或搜尋樹或圖的演算法。這個演算法會盡可能深地沿著圖的分支進行搜尋。當節點 v 的所有邊都己被探尋過，搜尋將回溯到發現節點 v 的那條邊的起始節點。這個過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點並重複以上過程，整個進程反覆進行直到所有節點都被訪問為止。
2. 廣度優先搜尋法 (BFS)：是一種圖形遍歷演算法，從一個給定的起始節點開始，首先訪問與該節點直接相連的所有鄰居節點。接著，對這些鄰居節點的鄰居進行遍歷，也就是以層次（Level）為基礎，由近而遠逐層向外擴展。在走訪完距離起點為 k 的所有節點之前，不會走訪距離為 k+1 的節點。

1. DFS 實作所需的資料結構：堆疊 (Stack)。原因：DFS 的特性是「後進先出 (LIFO)」，當探索到一個節點時，會先將其相鄰的未走訪節點推入堆疊中，接著馬上從堆疊頂端取出一個節點繼續深入探索，如果走到死胡同，可以藉由堆疊特性退回 (Backtracking) 到上一個有其他分支的節點。
2. BFS 實作所需的資料結構：佇列 (Queue)。原因：BFS 的特性是「先進先出 (FIFO)」，必須按層次順序訪問節點。當訪問一個節點時，將其所有相鄰的未走訪節點加入佇列尾端，然後從佇列前端取出下一個節點來處理，這樣可以保證較早發現的層級節點會先被處理。

根據圖 1 建立鄰接表（排序）： 1: 2, 8, 11 2: 1, 5, 6