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(子状态)
}
}
}
}
网友评论