BFS and DFS

BFS

广度优先搜索（Breadth-First-Search），我们平常都把简称为 BFS。直观地讲，它其实就是一种“地毯式”层层推进的搜索策略，即先查找离起始顶点最近的，然后是次近的，依次往外搜索。理解起来并不难，所以我画了一张示意图，你可以看下。

时空分析

每个节点入队和出队一次, 循环总次数为0(V), 检查邻接表所有的次数为O(E), 总时间为 O(V+E)

最短路径(无权最短路径)

距离定义：从 s 到 v 经过的最少的边, 记为 d(s,v), 不可达 d(s,v) -> +inf
引理: \[ \forall(u,v) \in E, \ d(s,v) \leq d(s,u) + 1\]

from collections import deque

def BFS(graph, s, t):
    visited = [None] * len(graph)
    prev = [-1] * len(graph)
    queue = deque()

    queue.append(s)
    visited[s] = True

    while queue:
        s = queue.popleft()
        for node in graph[s]:
            if not visited[node]:
                prev[node] = s
                if node == t:
                    return prev
                visited[node] = True
                queue.append(node)

    return None


def print_path(prev,s,t):
    if prev[t] != -1 and s != t:
        print_path(prev,s, prev[t])
    print(str(t), end = " ")




if __name__ == '__main__':
    g = {0:[1,3],1:[0,2,4],2:[1,5],3:[0,4],4:[1,3,5,6],5:[2,4,7],6:[4,7],7:[5,6]}
    prev = BFS(g,0,7)
    print_path(prev,0,7)

visited是用来记录已经被访问的顶点，用来避免顶点被重复访问。如果顶点 q 被访问，那相应的 visited[q] 会被设置为 true。
queue是一个队列，用来存储已经被访问、但相连的顶点还没有被访问的顶点。因为广度优先搜索是逐层访问的，也就是说，我们只有把第 k 层的顶点都访问完成之后，才能访问第 k+1 层的顶点。当我们访问到第 k 层的顶点的时候，我们需要把第 k 层的顶点记录下来，稍后才能通过第 k 层的顶点来找第 k+1 层的顶点。所以，我们用这个队列来实现记录的功能。
prev用来记录搜索路径。当我们从顶点 s 开始，广度优先搜索到顶点 t 后，prev 数组中存储的就是搜索的路径。不过，这个路径是反向存储的。prev[w] 存储的是，顶点 w 是从哪个前驱顶点遍历过来的。比如，我们通过顶点 2 的邻接表访问到顶点 3，那 prev[3] 就等于 2。为了正向打印出路径，我们需要递归地来打印，你可以看下 print() 函数的实现方式。

DFS

深度优先搜索（Depth-First-Search），简称 DFS。最直观的例子就是“走迷宫”。

假设你站在迷宫的某个岔路口，然后想找到出口。你随意选择一个岔路口来走，走着走着发现走不通的时候，你就回退到上一个岔路口，重新选择一条路继续走，直到最终找到出口。这种走法就是一种深度优先搜索策略。

实际上，深度优先搜索用的是一种比较著名的算法思想，回溯思想。这种思想解决问题的过程，非常适合用递归来实现。

时空分析

深度优先搜索算法的消耗内存主要是 visited、prev 数组和递归调用栈。visited、prev 数组的大小跟顶点的个数 V 成正比，递归调用栈的最大深度不会超过顶点的个数，所以总的空间复杂度就是 O(V)。

深度优先搜索算法的时间复杂度是 O(E)，E 表示边的个数。



import copy

def print_path(prev,s,t):
    if prev[t] != -1 and s != t:
        print_path(prev,s, prev[t])
    print(str(t), end = " ")

def DFS(graph,s,t):
    visited = [None] * len(graph)
    prev = [-1] * len(graph)
    visited[s] = True

    res,flag = None, False

    def recur_dfs(graph,s,t, prev, visited):
        nonlocal res, flag

        if flag:
            return 

        if s == t:
            flag = True
            res = copy.copy(prev)
            return

        for node in graph[s]:
            if not visited[node]:
                prev[node] = s
                visited[node] = True
                recur_dfs(graph,node,t,prev,visited)
                prev[node] = -1
                visited[node] = False

    recur_dfs(graph,s,t, prev, visited)

    return res


if __name__ == '__main__':
    g = {0:[1,3],1:[0,2,4],2:[1,5],3:[0,4],4:[1,3,5,6],5:[2,4,7],6:[4,7],7:[5,6]}
    res = DFS(g,0,7)
    print_path(res,0,7)