[FGISC。Nanro] 未來開端

DFS，深度優先搜尋(Depth First Search)的簡稱，又稱為縱向搜尋法。

＊什麼是DFS？
    顧名思義，是以Depth，也就是深度為優先考量的一種搜尋法。
    所謂的搜尋法，在圖論中，就是把所有的節點(node)走一遍的方法。
    也就是我以走得深為優先考量，當遇到末端時才走向其他的路。
    不過重點是在於「比這層深」，而不是在於「哪條比較深」
    所以只要是比自己深的點就可以走
    因為在一個點的時候，我們只會知道有跟它連接的路有哪些，
    而不知道那些通往哪裡。

    另外，DFS通常也會有著「循序」、「漸增」的特質
    也就是當我們要從1開始走，可以走的點有3 4 5三個
    那麼我們會先走到3，然後等到三那條走到底了，才會回來走4
    同理走完4才會走5這樣。

    還有就是，他的用途非常廣泛，不一定要侷限用於「圖的搜尋」
    一般像是排列組合、尤拉路徑、八皇后問題等等的，都可以用到DFS
    不過深入的部份留給下回再談。

＊從圖型來看
    現在我們有一個圖型如下：
          5
        ／ ＼
    1－2－4－8
     ＼         ／｜
          3－6－7

    假設起點是1，連接的點有2和3，那麼以深度優先往下看會先走到2
          5
        ／ ＼
    1－2－4－8
     ＼         ／｜
          3－6－7
    以2有連接的點來說：
    1.走走過的點一定是繞路
    2.以深度優先為考量
    3.循序漸增的特質
    所以在4.5之中我們會先走到4
          5
        ／ ＼
    1－2－4－8
     ＼        ／ ｜
          3－6－7
    4就沒有什麼好疑惑的了，往下繼續便可以走到8
          5
        ／ ＼
    1－2－4－8
     ＼         ／｜
          3－6－7
    以8來說呢，他會在5 6 7之中先走到5
    可是走到5就可以發現：沒有其他未走過而且可以走的路可以走
    這時我們便有一個back倒退的動作；也就是會回到上一個「仍有其他路可走」的點
    所以走過5之後，便又會走回8

    //順帶一提，back回去的這個動作，一般來說我們稱為backtracing，也就是回溯
    //其意義就是搜尋所有可能解，並於失敗時回到上一步再找其它可能解

    而這時8，就可以選擇往6走去
          5
        ／ ＼
    1－2－4－8
     ＼         ／｜
          3－6－7
    這時6就可以走到3或7

    同樣地先走3，然後發現3沒法走其他路
    就會退回6
    然後走到7 這時所有的點就都被走完了
    我們來看一下只保留走過路徑的圖形：
          5
           ＼
    1－2－4－8
           ／
       3－6－7
    而其拜訪順序則為1 2 4 8 5 6 3 7

    /****************************************************************/
    /* 練習時間                                                    　　　　　　　　 */
    /*         5－7                                                 　　　　　　　　　*/
    /*  (1)  ／|   ＼       其深度優先搜尋的拜訪順序為何？       　   */
    /*      1－3－4－6                                              　　　　　　　*/
    /*          ＼   |                                              　　　　　 　　　　*/
    /*            8－9                                              　　　　　  　　　*/
    /*  (2) 1-2-3-4-8                                     　        　　　　  　　*/
    /*       \   /                                                                                        */
    /*      7-5-6                                                                                     */
    /****************************************************************/

＊實做的方式
    一般而言，我們會使用遞迴或是堆疊、串列的方式來實做
    普遍來說以使用遞迴較為簡單、乾淨，也能讓程式呈現簡潔有力的感覺。
    至於路徑，也就是有沒有路，我們也可以使用二維陣列來表現
         1 2 3 4 5        5
      1 0 1 0 1 1       / \
      2 1 0 0 1 0      1-2 3   像左邊那樣的一個二維陣列，
      3 0 0 0 1 1        \ | /    就可以表示這個圖
      4 1 1 1 0 0         4
      5 1 0 1 0 0
    補充：
         遞迴其實在電腦裡面是在幕後幫你做好了很多事情。
         早期的程式語言並不支援遞迴的概念
         實際上遞迴是有用到堆疊的暫存區的

好，簡單的概念到這裡結束
較深入的應用我們下回分解。

Modified in 2007/09/11
Thanks to sa072686~