Kotlin 中的广度优先搜索算法

1. 简介

广度优先搜索（Breadth-First Search，BFS） 是图或树结构遍历与搜索的基础算法之一。它从指定的起始节点出发，优先访问当前深度的所有相邻节点，再逐步深入下一层。这种“逐层扩展”的特性，使 BFS 成为在无权图中寻找最短路径的理想选择。

本文将介绍如何在 Kotlin 中实现 BFS 算法，并通过实际代码演示其应用。

2. 理解 BFS

BFS 的核心思想是逐层访问节点。从起始节点开始，首先访问其所有相邻节点，再依次访问这些相邻节点的邻居，依此类推，直到图中所有可达节点都被访问。

✅ 特点：

使用队列（FIFO）管理待访问节点
保证访问路径最短（在无权图中）
可用于判断连通性、拓扑排序、最短路径等问题

⚠️ 注意： 在有环图中，必须记录已访问节点，防止重复访问陷入死循环。

3. Kotlin 中的 BFS 实现

3.1 定义图结构

我们使用邻接表（Adjacency List）表示图，这是图结构中常用且高效的表示方式。下面是一个示例图：

val graph = mutableMapOf<Int, List<Int>>(
    1 to listOf(2, 3, 4),
    2 to listOf(5, 6),
    3 to listOf(),
    4 to listOf(7, 8),
    5 to listOf(),
    6 to listOf(),
    7 to listOf(),
    8 to listOf()
)

图的结构如下所示：

      1
   /  |  \
  2   3   4
 / \     / \ 
5   6   7   8

3.2 BFS 实现代码

下面是 BFS 的 Kotlin 实现：

fun bfs(graph: Map<Int, List<Int>>, start: Int): Set<Int> {
    val visited = mutableSetOf<Int>()
    val queue = ArrayDeque<Int>()

    queue.add(start)

    while (queue.isNotEmpty()) {
        val vertex = queue.removeFirst()
        if (vertex !in visited) {
            visited.add(vertex)
            graph[vertex]?.let { neighbors ->
                queue.addAll(neighbors.filterNot { it in visited })
            }
        }
    }

    return visited
}

这段代码体现了 BFS 的核心流程：

使用 visited 集合记录已访问节点
使用 ArrayDeque 实现队列结构
每次从队列取出一个节点，访问后将其未访问的邻居加入队列

3.3 实现细节说明

初始化： 创建 visited 和 queue，将起始节点加入队列
主循环： 队列不为空时持续取出节点进行处理
节点访问： 若未访问过，则标记为已访问，并将其邻居加入队列
邻居处理： 使用 filterNot 确保只添加未访问过的节点，避免重复访问
结束条件： 队列为空时，遍历结束

这个实现确保了节点按照距离起始点的远近依次被访问，体现了 BFS 的“广度优先”特性。

4. 测试 BFS 实现

为了验证我们的 BFS 实现是否正确，我们可以编写一个 JUnit 单元测试：

@Test
fun `test BFS traversal order`() {
    val graph = mapOf(
        1 to listOf(2, 3, 4),
        2 to listOf(5, 6),
        3 to listOf(),
        4 to listOf(7, 8),
        5 to listOf(),
        6 to listOf(),
        7 to listOf(),
        8 to listOf()
    )

    val traversalOrder = bfs(graph, 1)

    val levelOne = listOf(traversalOrder.first())
    assertThat(levelOne).containsExactly(1)

    val levelTwo = traversalOrder.drop(1).take(3)
    assertThat(levelTwo).containsExactlyInAnyOrder(2, 3, 4)

    val levelThree = traversalOrder.drop(4)
    assertThat(levelThree).containsExactlyInAnyOrder(5, 6, 7, 8)
}

这个测试验证了：

第一层节点为 [1]
第二层节点为 [2, 3, 4]
第三层节点为 [5, 6, 7, 8]

测试通过说明我们的 BFS 实现是正确的。

5. 总结

通过在 Kotlin 中实现 BFS 算法，我们不仅掌握了图遍历的基本方法，也利用 Kotlin 的语法特性（如 ArrayDeque、Map、集合操作等）写出简洁高效的代码。

✅ BFS 的典型应用场景包括：

无权图中的最短路径查找
图的连通性判断
层次遍历（如树结构）
网络爬虫、社交关系扩散等

随着 Kotlin 在后端、Android 和服务端开发中的广泛应用，掌握其图算法实现，对解决实际问题具有重要意义。

完整代码可在 GitHub 仓库获取。

Persistence

REST

Security