BFS/DFS python模板与实现

BFS

BFS在搜索完第k层的节点之前，是不会搜索第k+1层的节点的。

BFS原理

BFS所用的是队列。把每个还没有搜索到的点依次放入队列，然后再弹出队列的头部元素当做当前遍历点。
搜索完这个点，就不会再对这个点进行搜索了。所以直接从队列中删掉就行。

模板

1. 无需分层遍历

while queue 不空：
    cur = queue.pop()
    for 节点 in cur的所有相邻节点：
        if 该节点有效且未访问过：
            queue.push(该节点)

'''
树的遍历
'''
from collections import deque

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


def level_order_tree(root, result):
    if not root:
        return
    # 这里借助python的双向队列实现队列
    # 避免使用list.pop(0)出站的时间复杂度为O(n)
    queue = deque([root])
    while queue:
        node = queue.popleft()
        # do somethings
        result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result


if __name__ == "__main__":
    tree = TreeNode(4)
    tree.left = TreeNode(9)
    tree.right = TreeNode(0)
    tree.left.left = TreeNode(5)
    tree.left.right = TreeNode(1)

    print(level_order_tree(tree, []))
    # [4, 9, 0, 5, 1]

'''
图的遍历
'''
from collections import deque
def bsf_graph(root):
    if not root:
        return
    # queue和seen为一对好基友，同时出现
    queue = deque([root])
    # seen避免图遍历过程中重复访问的情况，导致无法跳出循环
    seen = set([root])
    while queue:
        head = queue.popleft()
        # do somethings with the head node
        # 将head的邻居都添加进来
        for neighbor in head.neighbors:
            if neighbor not in seen:
                queue.append(neighbor)
                seen.add(neighbor)
    return xxx

2. 确定当前遍历到了哪一层

level = 0
while queue 不空：
    size = queue.size()
    while (size --) {
        cur = queue.pop()
        for 节点 in cur的所有相邻节点：
            if 该节点有效且未被访问过：
                queue.push(该节点)
    }
    level ++;

'''
树的遍历
'''
def level_order_tree(root):
    if not root:
        return
    q = [root]
    while q:
        new_q = []
        for node in q:
            # do somethins with this layer nodes...
            # 判断左右子树
            if node.left:
                new_q.append(node.left)
            if node.right:
                new_q.append(node.right)
        # 记得将旧的队列替换成新的队列
        q = new_q
    # 最后return想要返回的东西
    return xxx

'''
图的遍历
'''
def bsf_graph(root):
    if not root:
        return 
    queue = [root]
    seen = set([root])
    while queue:
        new_queue = []
        for node in queue:
            # do somethins with the node
            for neighbor in node.neighbors:
                if neighbor not in seen:
                    new_queue.append(neighbor)
                    seen.add(neighbor)
    return xxx

---

DFS

DFS尽可能深的搜索每个树枝，一直搜索到最深的那一个为止。

DFS原理

当DFS走到一条死路（再也没有可能的合法移动的方式）时，它会沿着树返回直到该节点有路可走。然后继续往深处探索。
DFS用的是栈。搜了k层的点a，再搜k+1层的点b，再 搜k+2层的点c。搜到c时，当前点标记为b，搜完c若返回false，那么就会回来从b再向下别的方向进行搜索。搜索了这个点，还可能回来再搜这个点向下的别的方向。

• 模板

'''
递归
'''
visited = set()

def dfs(node, visited):
    if node in visited:
        return
    visited.add(node)
    
    for next_node in node.children():
        if not next_node in visited:
            dfs(next_node, visited)

def DFS(self, tree):
    if tree.root is None:
        return []
        
    visited, stack = [], [tree.root]
    
    while stack:
        node = stack.pop()
        visited.add(node)
        
        process(node)
        nodes = generate_related_nodes(node)
        stack.push(nodes)

Reference

[1] https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/tao-mo-ban-bfs-he-dfs-du-ke-yi-jie-jue-by-fuxuemin/
[2] https://www.cnblogs.com/bham/p/11746312.html