广度和深度优先搜索

图系列文章链接：

图的存储 (Jul 18, 2021)
广度和深度优先搜索 (Jul 18, 2021)
A*启发式搜索 (Jul 18, 2021)

算法是作用于具体数据结构之上的，深度优先搜索算法、广度优先搜索算法和A*启发式搜索都是基于“图”这种数据结构的。

广度优先搜索和深度优先搜索也被叫作暴力搜索算法，这两种搜索算法仅适用于状态空间不大，也就是说图不大的搜索。
- 广度优先搜索需要借助队列来实现，遍历得到的路径就是，起始顶点到终止顶点的最短路径。
- 深度优先搜索用的是回溯思想，非常适合用递归实现。换种说法，深度优先搜索是借助栈来实现的。

基于邻接表的无向图的实现

type Graph struct { // 无向图
    adj []*list.List // 邻接表
    v   int      //顶点个数
    isFound bool     //默认值为false
}

func newGraph(v int) *Graph {
    graphh := &Graph{}
    graphh.v = v
    graphh.adj = make([]*list.List, v)
    for i := range graphh.adj {
        graphh.adj[i] = list.New()
    }
    return graphh
}

func (self *Graph) addEdge(s int, t int) { //无向图一条边存2次
    self.adj[s].PushBack(t)
    self.adj[t].PushBack(s)
}

广度优先算法（BFS）

广度优先搜索（Breadth-First-Search），我们平常都简称 BFS。

直观地讲，它其实就是一种“地毯式”层层推进的搜索策略，即先查找离起始顶点最近的，然后是次近的，依次往外搜索。

func (self *Graph) BFS(s int, t int) { // s 表示起始顶点，t 表示终止顶点
    if s == t {
        return
    }

    visited := make([]bool, self.v)
    visited[s] = true
    queue := list.New()
    queue.PushBack(s)
    prev := make([]int, self.v)
    for index := range prev {
        prev[index] = -1
    }

    for queue.Len() != 0 {
        w := queue.Front() //出队
        queue.Remove(w)
        wv, ok := w.Value.(int)
        if !ok {
            log.Fatal("type of w in queue is not int")
        }

        for e := self.adj[wv].Front(); e != nil; e = e.Next() {
            q := e.Value.(int)
            if !visited[q] {
                prev[q] = wv
                if q == t {
                    printPrev(prev, s, t)
                    return
                }
                visited[q] = true
                queue.PushBack(q)
            }
        }
    }
    fmt.Printf("no path found from %d to %d\n", s, t)
}

func printPrev(prev []int, s int, t int) {
    if prev[t] != -1 && t != s {
        printPrev(prev, s, prev[t])
    }
    fmt.Printf("%d ", t)
}

只要理解了三个重要的辅助变量 visited、queue、prev，上面的代码就能看懂了：

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。
- 为了正向打印出路径，我们需要递归地来打印，你可以看下 printPrev() 函数的实现方式。

时间复杂度分析：

最坏情况下，终止顶点 t 离起始顶点 s 很远，需要遍历完整个图才能找到。
- 这个时候，每个顶点都要进出一遍队列，每个边也都会被访问一次，所以，广度优先搜索的时间复杂度是 O(V+E)，其中，V 表示顶点的个数，E 表示边的个数。
- 当然，对于一个连通图来说，也就是说一个图中的所有顶点都是连通的，E 肯定要大于等于 V-1，所以，广度优先搜索的时间复杂度也可以简写为 O(E)。

空间复杂度分析：

空间消耗主要在几个辅助变量 visited 数组、queue 队列、prev 数组上。这三个存储空间的大小都不会超过顶点的个数，所以空间复杂度是 O(V)。

深度优先算法（DFS）

类似“走迷宫”，假设你站在迷宫的某个岔路口，然后想找到出口。你随意选择一个岔路口来走，走着走着发现走不通的时候，你就回退到上一个岔路口，重新选择一条路继续走，直到最终找到出口。

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

func (self *Graph) DFS(s int, t int) {
    self.isFound = false  // 这句代码非常重要，否则，第二次调用DFS函数的时候就会报错
    visited := make([]bool, self.v)
    prev := make([]int, self.v)
    for i := range prev { prev[i] = -1 }

    self.recurse(s, t, prev, visited)
    printPrev(prev, s, t)
}

func (self *Graph) recurse(w int, t int, prev []int, visited []bool) {
    if self.isFound { return }
    visited[w] = true

    if w == t {
        self.isFound = true
        return
    }

    for e := self.adj[w].Front(); e != nil; e = e.Next() {
        q := e.Value.(int)
        if !visited[q] {
            prev[q] = w
            self.recurse(q, t, prev, visited)
        }
    }

}

空间复杂度分析：

每条边最多会被访问两次，一次是遍历，一次是回退。所以，图上的深度优先搜索算法的时间复杂度是 O(E)，E 表示边的个数。

空间复杂度分析：

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

专题: 图

本文发表于 2021-07-18，最后修改于 2021-07-18。

本站永久域名「 jiavvc.top 」，也可搜索「后浪笔记一零二四」找到我。

上一篇 « 图的存储下一篇 » A*启发式搜索

广度和深度优先搜索

基于邻接表的无向图的实现

广度优先算法（BFS）

深度优先算法（DFS）

推荐阅读