今天想要探討一下關於Graph裡面的DFS、BFS、Stack Treversal以及Binary Tree的Preorder、InOrder、PostOrder Traversal。
先看一下DFS的Iterative代碼
def dfs(graph, node):
parents = {node:None}
visited = {}
stack = [node]
while stack:
v = stack.pop()
if not v in visited:
visited[v] = parents[v]
for a in reversed(graph[v]):
stack.append(a)
parents[a] = v
print(v, ''.join(stack))
return visited
DFS代碼最重要的是使用stack並且拿出最後一個node出來，然後檢查確認這個node沒有曾經處理過的話才會被“搜全家”並且放進stack等待處理，換句話說如果這個node曾經被處理過的話下次再遇到的話它就會被忽略掉。那麼什麼時候一個node在stack拿出來的時候就已經被處理過呢？唯一的可能性就是一個node被重複放到stack裡面，第一次拿出來的時候沒有處理過，第二次拿出來的時候就知道已經處理過了。Wikipedia也寫著"DFS has worst case O(|E|) with possible duplication of nodes on the stack"。
舉個例子掌心對著自己的那5隻手指全部互聯的話會產生5角形以及5角星合共10條邊，在第一次iteration處理拇指之後stack裡面就有4根手指，在第二次iteration處理食指之後stack除了原有拇指連著的的中無尾3根手指之外又要添加4根重複的母中無尾手指合共7根手指。stack裡面最長的暫存資料是5435454321或者“尾無中尾無尾無中食母”，剛好是10個資料並且是合共的10條邊。
正因為node可以被多次重複放進stack，所以才能夠過讓stack裡面的node“走得更遠”，並且達到最大的深度。DFS會從第一個分支的頭部開始一邊蔓延一邊儲存在stack裡面直到末端，然後才跑到第二個分支。
再來看一下BFS的Iterative代碼
def bfs(graph, node):
parents = {node:None}
visited = {node:None}
deque = collections.deque([node])
while deque:
v = deque.popleft()
for a in reversed(graph[v]):
if a not in visited:
parents[a] = v
visited[a] = parents[a]
deque.append(a)
print(v, ''.join(deque))
return visited
BFS的代碼特點除了使用queue代替stack去暫存資料之外，它的處理方法是先“搜全家”然後確認沒有被處理過才會被放進暫存queue裡面，而且由於全部node都會確認沒有被處理過才放進去queue裡面，因此queue裡面不可能有重複的node，而且每一個node都只會被放進queue裡面1次而不是多次。
Stack Traversal
BFS與DFS看起來有點相似的，的確它們都是用來搜索整顆樹，但是他們的特點都是有各自的優先的。假設在BFS的演算法裡面的queue換成stack就會變成DFS嗎？不會啊，姑且叫它做stack traversal，雖然兩者都可以搜索整顆樹，但是stack traversal不是深度優先。
深度優先的演算法的重點在於每個node的“全家”會被無條件添加到stack裡面，至於要不要處理就等到他們的從stack拿出來的時候才檢查，越遲檢查的話stack的深度就越長，達到深度優先的效果。
那麼stack traversal為什麼不是深度優先？stack traversal將BFS的queue換成stack，僅此而已。因此BFS的其中一個特質被保留：先檢查node沒有處理過才會放進暫存的stack或者queue，因此接近七點的node的家人一早就被認定已經處理過了，而且這些node只會被放進暫存最多1次而不是多次，因此其後如果發現有backedge的話那些node不會在被放進暫存了，因此深度被中斷了，也因此不是深度優先。
比較DFS與BFS
DFS的精髓在於允許node重複放進暫存，並且等到拿出來的時間才檢查是否曾經處理過，因此暫存的stack增長的很快很深而且有重複。
BFS則是先檢查是否曾經處理過才放進暫存queue的，而且不允許重複放進queue裡面，因此queue裡面的資料就是“沿著起點繞圈”往外擴展，也許將BFS叫做Sprial Search更為生動一些。
Preorder
Preorder使用“上左右”的方法穿越整顆樹，其實就是用DFS的無HashMap版本。不需要HashMap的原因是因為BinaryTree沒有backedge不會存在一個node被處理多次。
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
answer = []
stack = [root]
while stack:
node = stack.pop()
if node:
answer.append(node)
stack.append(node.right)
stack.append(node.left)
return answer
Postorder
Postorder使用“左右上”的方法穿越整顆樹，其實也是使用DFS的無HashMap版本。Postorder與Preorder都是從上到下穿越整顆樹的，只是最後結果需要反向一次。
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
answer = []
stack = [root]
while stack:
node = stack.pop()
if node:
answer.append(node.val)
stack.append(node.left)
stack.append(node.right)
return reversed(answer)
Inorder
Inorder使用的方法是先靠左DFS，去到盡頭之後將指針往右移動，然後繼續DFS。演算法運行起來像中文字的”久“。
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
# func(left)+[val]+func(right)
answer = []
stack = []
while stack or root:
if root:
stack.append(root)
root = root.left
else:
node = stack.pop()
if node:
answer.append(node)
root = node.right
return answer
End
沒有留言:
張貼留言