(わかりやすい)『面接』--広さ優先検索(BFS)と深さ優先検索(DFS)Python実現

前言
どちらも古典的な図探索アルゴリズムとして、図中のすべてのノードを系統的に展開して検査することを目的としているが、この2つのアルゴリズムは異なる探索方式を持ち、二叉木を探索することを例に(二叉木も実は特殊な図構造である)、広さ優先探索(BFS)は上から下へ探索し,上の層のすべてのノードが遍歴してから次の層に移るのを待つだけであり,深さ優先探索(DFS)は最初から奥へ進み,解が見つかるか底部まで進む.
広さ優先探索(BFS)
BFS思想(二叉木を例に)
1、ルートノードから;
2、ノードをキューに保存する
3、キューの先頭ノードを取り出し、そのノードの値を読み取り、子供ノードがあるかどうかを判断し、あれば順番にキューの末尾に追加する
4、キューが空になるまで3回繰り返します

#        
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


def BFS(node):
    #           
    if node is None:
        return None

    queue = [node]
    result = []

    while len(queue):
        cnt = queue.pop(0)        #          
        result.append(cnt.val)    #        

        if cnt.left:              #          ，         
            queue.append(cnt.left)

        if cnt.right:             #          ，         
            queue.append(cnt.right)
    return result


if __name__ == '__main__':
    a = TreeNode(0)
    b = TreeNode(1)
    c = TreeNode(2)
    d = TreeNode(3)
    e = TreeNode(4)
    f = TreeNode(5)
    g = TreeNode(6)
    a.left = b
    a.right = c
    b.left = d
    b.right = e
    c.left = f
    c.right = g

    print(BFS(a))

深度優先検索(DFS)
DFS思想(二叉木を例に):
1、ルートノードをスタックデータ構造に入れる
2、スタックから最初のノードを取り出し、子供ノードがあるかどうかを判断し、ある場合はそのノードの未検索の子供ノードをstackに入れる
3、手順2を繰り返す

def DFS(node):
    #            
    if not node:
        return None

    stack = [node]          #    
    nodeSet = set()         # set  ，          
    nodeSet.add(node)       #        ，     set 
    result = [node.val]
    while len(stack):
        cur = stack.pop()
        for nextNode in (cur.left, cur.right):      #         ，          
            if nextNode is not None and nextNode not in nodeSet:    #            
                #                    ，        
                stack.append(cur)
                stack.append(nextNode)              #              
                nodeSet.add(nextNode)               #         set      
                result.append(nextNode.val)
                break                               #   ，      
    return result

疑問:
1、なぜcurを弾いた後、curをスタックに押し込むのですか.
答え:スタックの順序が深さ優先で検索されることを保証するために、curにサブノードがない場合は、スタックを直接ポップアップします.サブノードがある場合は、curスタックを先に圧縮してからcurサブノードスタックを圧縮すると、スタックの上部のノードに親ノードがあることを保証できます(親ノードの他のサブノードを遍歴するのに便利です).
2、なぜbreak文を付ける必要があるのですか.
深度を優先し、ノード(node)に左サブノード(left)と右サブノード(right)があり、左サブノードにサブノード(leftch)があると仮定します.
breakがない場合のスタック順序がnode-left-right-leftchであり、同様に遍歴順序もnode-left-right-leftchであり、DFSには明らかに合致しない
breakがある場合、スタックの変化は次のとおりです.
1、node--left--leftch(leftchにはサブノードがなく、次はスタックを弾き始める)
2、node--left(leftのサブノードはすでに遍歴され、スタックを弾き続ける)
3、node(nodeのサブノードleftは既に遍歴されているが、右のサブノードは遍歴していないので、次はrightスタックを押す)
4、node -- right
明らかに深さ優先の法則に合致している.