連假結束，開工第一天，用寫IT邦來收收心

圖的走訪

圖的走訪是一項重要的操作，主要有兩種方法：深度優先搜尋（Depth First Search，DFS）和廣度優先搜尋（Breadth-First Search，BFS）。

深度優先搜索（DFS）

DFS是一種用於圖形和樹狀結構的搜索算法，用於探索所有可能的節點，直到找到目標節點或遍歷整個結構。DFS的主要思想是先往深處探索，然後回溯到之前的節點，再繼續向下一個分支探索。

基本工作原理

1. 選擇起始節點：首先，選擇一個起始節點，並將其標記為已訪問。
2. 探索鄰近節點：從起始節點開始，選擇一個鄰近節點，並標記為已訪問。如果有多個相鄰節點，通常選擇第一個未訪問的節點。
3. 遞迴探索：對所選節點重複步驟2，一直向深處探索，直到達到一個無法再往下探索的終止節點，或者達到目標節點。
4. 回溯：當達到無法再向下探索的節點或目標節點後，回溯到之前的節點，再選擇一個未訪問的相鄰節點繼續探索。
5. 重複過程：重複以上步驟，直到遍歷完整個圖形或找到目標節點為止。

DFS的實現方式可以使用遞迴或堆疊（或稱為堆棧）來追蹤節點的訪問順序。在使用遞迴的情況下，程式會自動維護呼叫堆疊，而在使用堆疊的情況下，你需要手動管理堆疊。

圖解

我們會先往深處探索，然後回溯到之前的節點

程式碼

void DFS::DFS_Traversal(int s) {
    vector<bool> visited(V, false); // 設定所有頂點都沒有被訪問過
    stack<int> stack; // 建立一個堆疊
    stack.push(s); // 將起始頂點放入堆疊
    visited[s] = true; // 設定起始頂點為已訪問
    while (!stack.empty()) { // 當堆疊不為空
        int v = stack.top(); // 取出堆疊頂點
        cout << v << " "; // 印出頂點
        stack.pop(); // 將頂點從堆疊中移除
        for (auto i = adj[v].begin(); i != adj[v].end(); i++) { // 對於頂點v的每一個鄰接頂點
            if (!visited[*i]) { // 如果鄰接頂點沒有被訪問過
                stack.push(*i); // 將鄰接頂點放入堆疊
                visited[*i] = true; // 設定鄰接頂點為已訪問
            } 
        }
    }
}

優點

• 簡單易實現。
• 適用於樹狀結構和圖形。
• 可用於解決深度搜索問題，如找到路徑或達到目標節點。

缺點

• 可能會陷入無限迴圈，如果圖中包含循環。
• 當圖形深度很大時，遞迴可能導致堆疊溢出。
• 沒有保證找到最短路徑，因為它優先探索深處，而不是最接近起始節點的節點。

深度優先搜尋是一種重要的搜尋算法，常常用於解決迷宮、拓撲排序、圖形遍歷等問題。在實際應用中，你可以根據具體問題的需求來選擇使用深度優先搜尋或其他搜尋算法。

廣度優先搜尋（BFS）

BFS是一種搜尋算法，用於圖形和樹狀結構的探索。它的核心思想是先往相鄰的節點探索，然後逐層擴展到更遠的節點。

基本工作原理

以下是BFS的基本工作原理：

1. 選擇起始節點：首先，選擇一個起始節點，將其標記為已訪問。
2. 探索所有相鄰節點：從起始節點開始，依次訪問所有與其相鄰的節點，並將它們標記為已訪問。
3. 進一步擴展：對於每個已訪問的相鄰節點，再依次訪問它們的相鄰節點，依此類推，直到達到目標節點或遍歷整個圖。
4. 保持層級：BFS保持了節點的層級信息，即首先訪問起始節點，然後訪問與起始節點相鄰的節點，然後是它們的相鄰節點，以此類推。
   BFS通常使用佇列（Queue）來實現，以確保按層級順序進行訪問。

圖解

先往相鄰的節點探索，然後逐層擴展到更遠的節點

程式碼

void BFS::BFS_Traversal(int s) {
    vector<bool> visited(V, false); // 設定所有頂點都沒有被訪問過
    vector<int> queue; // 建立一個佇列
    queue.push_back(s); // 將起始頂點放入佇列
    visited[s] = true; // 設定起始頂點為已訪問
    while (!queue.empty()) { // 當佇列不為空
        int v = queue.front(); // 取出佇列頂點
        cout << v << " "; // 印出頂點
        queue.erase(queue.begin()); // 將頂點從佇列中移除
        for (auto i = adj[v].begin(); i != adj[v].end(); i++) { // 對於頂點v的每一個鄰接頂點
            if (!visited[*i]) { // 如果鄰接頂點沒有被訪問過
                queue.push_back(*i); // 將鄰接頂點放入佇列
                visited[*i] = true; // 設定鄰接頂點為已訪問
            } 
        }
    }
}

優點

• 可以找到最短路徑，因為它優先探索距離起始節點最近的節點。
• 不會陷入無限迴圈，即使圖中包含循環。
• 適用於解決最短路徑、最短距離和最小生成樹等問題。

缺點

• 需要較多的記憶體，因為需要記錄所有已訪問的節點。
• 在實珸中，可能需要使用佇列來實現，增加了程式碼的複雜性。

DFS與BFS 之比較

以下是深度優先搜索（DFS）和廣度優先搜索（BFS）之間的比較表

總結來說，DFS主要適用於深度搜索問題，如迷宮解決和拓撲排序，但不保證找到最短路徑。BFS則適用於需要找到最短路徑的情況，並且不會陷入無限迴圈，但需要更多的記憶體和較複雜的程式碼以使用佇列來實現。選擇哪種算法取決於您的具體問題需求。

每個人都有自己獨特的生活節奏和目標，不必受到他人的壓力或期望。重要的是要找到自己的方向，以自己的步伐前進，這樣你可以更自在、更快樂地探索世界。