棧DFS就是這麼簡單
一、背景
之前寫了五篇文章來講解了《 陣列就是這麼簡單 》系列,前天寫了一篇文章來講解《 佇列就是這麼簡單 》,昨天用一篇文章來介紹《 棧理論就是這麼簡單 》,今天來看看《棧DFS就是這麼簡單》吧。
理論知識
前面的文章我們知道了,棧是一種後進先出的資料結構。
通過棧能夠實現深度優先搜尋,從而可以用來解決樹、圖、以及搜尋上的問題。
對於圖,搜尋順序如下圖:
起始節點先入棧。
然後找選擇一個子節點路徑,直到盡頭。
接著,當前路徑的最後一個節點 G
處理完成後,會嘗試掃描倒數第二個節點 D
的其他兒子。
當倒數第二個節點的所有兒子處理完後,會嘗試掃描倒數第三個節點 B
的其他兒子。
如下圖,路徑變成了 A->B->E
。
接著, B
的所有兒子處理完了,就要回溯到 A
,然後處理 A
的其他兒子。
這樣就進入了路徑 A->C->F
了。
這路需要注意的是, E
節點我們已經處理過了,所以我們不會生成 A->C->E
路徑。
這樣,我們就模擬了深度優先搜尋 DFS
的過程,搜尋過程中,父節點的資訊儲存在棧中,從而能夠完成回溯搜尋。
當然,上面的模擬過程為了簡單,省略了一些東西。
實際使用的時候,如果一個父節點遍歷了子節點(遍歷後代表當前節點處理過),我們不會儲存在棧中。
棧中實際儲存的是尚未處理的節點資訊。
另外,對於棧的使用有兩種方法。
一種是自己使用資料結構棧來處理資料,一種是使用函式的遞迴形式來處理DFS相關的問題。
使用資料結構的好處是我們的棧可以很大,但是儲存的資訊有限。
使用函式遞迴的好處是我們可以儲存一個節點的上下文,在計算完所有子節點的時候,可以聚合出一個結果來(具體見下面的實踐題目:目標和),從而做到避免重複計算。
具體的實現可以看下面的實踐程式碼吧。
三、島嶼的個數
題意:輸入一個二維陣列,值是 0
海水或 1
陸地。陸地上下左右方向挨著時代表陸地連線著。
求互相獨立的島嶼個數。
思路:如果你看過之前的文章的話,就會發現這道題之前做過了。
上次是使用佇列把這道題解決了,現在需要使用棧來解決。
思路則是每次將相鄰的尚未處理的陸地加入到棧中,然後依次處理。
四、克隆圖
題意:給一個無向連通圖(指標),求深拷貝該圖。
題意:這裡除了要正常的遞迴外,還涉及一個問題:如何找到一個節點的指標。
這個使用 map
儲存起來即可,由於不知道 val
是否重複,儲存指標的對映關係最靠譜。
五、目標和
題意:給定一個非負整數陣列和一個目標數,我們可以給每個數賦予一個符號,問最終陣列和等於目標數的個數。
思路:假設有 N
個數字,每個數字有兩個符號,則共有 2^N
中組合情況。
由於是求方案個數,我們需要遍歷所有的組合情況。
所以問題轉化為了:如何遍歷組合數。
其實,對於組合問題,可以轉化為圖的遍歷問題。
比如這道題可以轉化為下圖,起點是 0
,可以到達第一個數的兩種情況,然後可以到達第二個數的兩種情況,直到最後。
對於搜尋問題,我們會發現有很多重複的搜尋。
比如 1 1 1 1 1
這個資料,到達第三個位置的時候,路徑和是 1
的情況有很多種。
比如
+ 1 + 1 - 1 + 1 - 1 + 1 - 1 + 1 + 1
此時,去搜索第四個位置的時候,都是使用字首和 1
在第四個位置上搜索。
這樣我們就會重複搜尋三次。
如果搜尋第一次的時候,就記錄下答案的話,後兩次即可直接得到結果。
每個位置和字首和組合起來才算一個狀態,所以我們使用位置和字首和來作為 map
的 key
。
具體參考下面的程式碼。
六、二叉樹的中序遍歷
題意:給定一個二叉樹,返回它的中序 遍歷。
要求:遞迴演算法很簡單,要求自己使用棧實現。
思路:先來看看遞迴的程式碼吧。
遞迴確實好簡單,那自己模擬棧了的時候面臨一個問題:我們不知道中間這個節點是首次出棧還是第二次出棧。
首次出棧的時候,我們需要找到左兒子。由於是中序,父節點還需要進入棧。
第二次出棧的時候,代表左兒子處理完了,父節點直接輸出到答案裡面,接著需要處理右兒子。
既然不知道,那就記錄下來。
記錄的這個其實就是上面提到的遞迴的上下文。
比如使用一個欄位來表示狀態, 0
代表首次出棧, 1
代表第二次出棧。
然後就可以寫出和遞迴一樣的程式碼了。
大家可以對比一下遞迴的實現和這個棧的實現。
七、最後
這篇文章簡單的介紹了棧的一些實踐題。
由於函式遞迴就是一種系統棧,所以一般情況下我們都是直接使用函式遞迴的解決問題的。
而對於那些不需要父節點與子節點上下文關係的場景,我們直接使用棧來處理也很方便。
大家到時候可以按照這個上下文關係為指標,來決定是使用棧還是使用遞迴吧。
-EOF-