广度和深度优先搜索

BFS、DFS主要是针对图这种数据结构来说的，记得以前大学第一次接触到这2种算法时，觉得理解起来很简单，但是代码确总写不好。回想起来，还是数据结构基础不扎实，当时总觉得图太复杂了，感觉无从下手，其实这些基本思想都可以在二叉树中找到原型。

1. BFS算法

我们先来说说二叉树，入门学习二叉树的时候，必然绕不开二叉树的遍历，通常有前序遍历、中序遍历、后序遍历，除此外还有一种就是层序遍历，层序遍历就是从根节点开始从上往下、从左往右一层层依次遍历节点，层序遍历其实就是广度优先算法。二叉树中一个节点最多只有左右两个子节点，我们把二叉树想象成一种特殊的图就可以了，图无非就是一个节点可能连接着多个节点。
如果你对二叉树的层序遍历算法很熟悉的话，那么图的广度优先算法基本上就可以信手拈来了，不熟悉的可以参考这篇文章：二叉树的几种遍历

/**
 * 无向图
 *
 * @param vertexCount 图的顶点数
 */
class Graph(private val vertexCount: Int) {

    /**
     * 用邻接链表来存储图
     */
    private val adjacencyList: Array<LinkedList<Int>> = Array(vertexCount) {
        LinkedList<Int>()
    }

    private var found = false

    /**
     * 添加图的边，对于无向图需要添加2次
     *
     * @param start 起始顶点
     * @param end 终止顶点
     */
    fun addEdge(start: Int, end: Int) {
        adjacencyList[start].add(end)
        adjacencyList[end].add(start)
    }

    /**
     * 广度优先搜索
     *
     * @param s 起始顶点
     * @param e 终止顶点
     */
    fun bfs(s: Int, e: Int) {
        if (s == e) {
            return
        }
        //记录每个顶点是否有访问过，初始默认值都是未访问 false
        val visited = BooleanArray(vertexCount) { false }
        //记录每个顶点的前驱顶点，初始默认值都是 -1
        val prev = IntArray(vertexCount) { -1 }
        //广度搜索，类似树的按层访问，用队列来辅助
        val queue = LinkedList<Int>()
        queue.add(s)
        visited[s] = true
        while (queue.isNotEmpty()) {
            //取出队头顶点 i
            var i = queue.poll()
            //取出顶点 i 的下一层相邻顶点
            var list = adjacencyList[i]
            //遍历顶点 i 的所有下一层顶点
            for (j in list) {
                if (!visited[j]) {
                    //记录前驱节点，顶点 m 的前驱顶点为 i
                    prev[j] = i
                    //如果找到终止顶点，则循环结束
                    if (e == j) {
                        printPath(prev, s, e)
                        return
                    }
                    //如果没有访问过
                    visited[j] = true
                    //没访问过的顶点入队
                    queue.offer(j)
                }
            }
        }

        println("未找到任何从顶点 $s 到顶点 $e 的路径.")
    }

    private fun printPath(prev: IntArray, s: Int, e: Int) {
        //先打印前驱顶点
        if (prev[e] != -1 && s != e)
            printPath(prev, s, prev[e])
        print(e)
    }
}

2. DFS算法

同样我们拿二叉树来说明，二叉树的前序、中序、后序遍历都有递归写法，DFS算法根本上与二叉树遍历的递归实现是一样的。
一般二叉树的后序遍历的伪代码如下：

postOrder(node) {
  //遍历左子节点
  postOrder(node.left)
  //遍历右子节点
  postOrder(node.right)
  //遍历当前节点
}

在二叉树中，只需要遍历节点的左、右2个子节点，而在图中，一个顶点会与多个顶点相连，我们只需要把与顶点相列的多个顶点依次遍历就可以了。

    /**
     * 深度优先搜索
     *
     * @param s 起始顶点
     * @param e 终止顶点
     */
    fun dfs(s: Int, e: Int) {
        if (s == e)
            return
        found = false
        val visited = BooleanArray(vertexCount) { false }
        val prev = IntArray(vertexCount) { -1 }
        recursive(s, e, visited, prev)
        if (found) {
            printPath(prev, s, e)
        } else {
            println("未找到任何从顶点 $s 到顶点 $e 的路径.")
        }
    }

    /**
     * 递归查找
     * 如果顶点 s 的邻接顶点有 n 个，我们用 next[n] 表示，要找到顶点 s 到顶点 e 的路径，
     * 遍历查找 (s - next[0], next[0] - e)，(s - next[1], next[1] - e)...(s - next[n-1], next[n-1] - e)
     * 反复递归下去，直到查找完毕
     */
    private fun recursive(s: Int, e: Int, visited: BooleanArray, prev: IntArray) {
        if (found)
            return
        visited[s] = true
        val list = adjacencyList[s]
        for (i in list) {
            //如果该顶点没有访问过
            if (!visited[i]) {
                prev[i] = s
                if (i == e) {
                    //已经找到
                    found = true
                    return
                }
                recursive(i, e, visited, prev)
            }
        }
    }

3. 小结

二叉树是很多算法的基础，很多其他算法都是在二叉树的基础上演化而来的。对于广度优先与深度优先算法，我们可以这样来记：

BFS：二叉树的层序遍历
DFS：二叉树的后序递归遍历

通常情况下，BFS 用来解决最短路径问题，DFS 是用来解决连通性问题的。

这里总结了 2 个模板，基本上大部分 BFS、DFS的问题都可以套用这2个框架来解决。

dfs(当前状态) {
    if (遇到边界条件 | 已找到结果) {
        return
    }
    //遍历当前状态所能到达的所有子状态
    for (int i = 0; i < n; i++) {
        if (子状态满足约束条件) {
            dfs(子状态)
        }
    }
}

bfs() {
    //定义一个队列 queue
    queue.offer(初始状态)
    while (queue不为空) {
        //取出队列头部的状态
        x = queue.poll()
        if(x为目标结果)
          return
        //遍历 x 的所有相邻状态
        for (int i = 0; i < n; i++) {
            if (子状态满足约束条件) {
                //加入到队列尾部
                queue.offer(子状态)
            }
        }
    }
}