天上的東東w

在上次趴one 裡面我們已經 以一棵彩虹樹(?) 來 解釋了 DFS 的基礎步驟，並且用 C++ 以及 Python 實作了相關的程式碼，這次我們要來看看圖的部分。 啊，在這之前，我們簡單的複習一下 DFS 的要素：           1) 選擇起始點           2) 進入 DFS 後，先判斷是否已經到終端，如果是的話，離開 DFS           3) 把這個節點設為已走訪過           4) 尋找下一個可行的節點並進入，回到 2) 圖 當然是要先畫一張圖啦：   為了方便討論，這是個無向圖，也就是每條路都是雙向道。那我們開始吧！一樣先選一個起點，這裡我們選  1 ，可以看到，與 1 相連的節點有  2  和  3  ，根據 DFS 的精神，我們一樣要選一個點來「 深 」入討論，這裡我們就選 2，並同時約定，之後若要從多個點選擇的話，以數字小的為優先。   於是我們拿 2 來進行下一次的 DFS，結果找到了  3 ,  4 。因為剛剛的約定，我們在這先選比較小的 3 來進行下一層的 DFS，並找到了  1 ,  5 ,    6   ， 咦？1 號節點我們剛剛不是走過了嗎？沒錯，所以我們這次就不用理他，直接選 5 繼續吧。   接著我們就找到了   4   和   6  ，我們再接著選 4，結果發現他找到的 2 在前面就走訪過了，因此我們就返回到 5，並選擇 6 重新出發。結果發現，走 6 這條路也沒辦法找到還沒走訪過的節點，因此退回到 5。   而 5 呢？也找不到新的節點了，所以再退，就這樣一路退到 1，發現完全沒有新的節點，因此，圖的 DFS 到此結束。 程式碼實作 C++ void dfs(int now){ cout << now << " visited." << endl; for (int i = 1; i <= 6; i++){ if (!visited[i] && e[now][i] == 1){ // 如果還沒來過而且可以走到 visited[i] = true; dfs(i);

我放棄把每 5 篇合在一起的想法了，那樣文章會變得很長ˊˇˋ 今天要介紹很好用的函式： atoi()、atol()：字串轉整數   所屬標頭檔： <stdlib.h>   函式宣告： int atoi( const char *str ); long atol( const char *str );   首先要注意到： 這次的標頭檔 並不是我們熟悉的 <string.h>，而是 <stdlib.h>。   這兩是個可以把字串中的有效部分轉換成整數、長整數的函式，而怎麼樣算有效呢？基本上要符合以下條件：           1) 可能有正負號 （+ / -）           2) 數字   如果這個字串的開頭有一些空格的話，這兩個函式會自動跳過；而如果在有效部分後面還有一些文字的話（例如小數點），函式將不會理會這些多餘的字。 atof()：字串轉浮點數   所屬標頭檔： <stdlib.h>   函式宣告： double atof( const char* str );   這兩是個可以把字串中的有效部分轉換成雙精度浮點數的函式，而怎麼樣算有效呢？基本上要符合以下條件：           1) 可能有正負號（+ / -）           2) 數字（可能有小數點）           3) 可能以「e」、「E」來表示的科學計號           4) 無限：inf 或 infinity（忽略大小寫）           5) 非數：NaN （忽略大小寫）   如果這個字串的開頭有 空格的話，這兩個函式會自動跳過；而如果在有效部分後面還有一些文字的話（ 不含 上述提到的記號），函式將不會理會這些多餘的字。   另外，如果沒辦法轉換的話，atoi()、atol() 會回傳 0，atof() 會回傳 0.0；而如果轉換後超出該型態可儲存的範圍，將會是 undefined behavior。   範例如下： #include <iostream> #include <cstdlib> #include <string> using namespace std; int main(){ cons