Kotlin中的广度优先搜索算法

Kahen大约 4 分钟

Kotlin中的广度优先搜索算法

广度优先搜索（BFS）是一种基本的算法，用于遍历或搜索树状或图状数据结构。它从选定的节点开始（在树结构中通常是根节点），然后探索当前深度的所有邻居节点，再移动到下一层深度的节点。BFS特别适用于在未加权图中找到最短路径。

在本教程中，我们将探索在Kotlin中实现BFS算法。

3.1. 定义图

首先，我们需要定义一个图。我们将使用邻接表，因为它是Kotlin中表示图的一种常见且有效的方式。此外，为了提供具体示例，我们将初始化我们的图，添加一些节点和边，以说明BFS在实践中的工作原理：

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

这张图表帮助我们可视化从根节点“1”开始的BFS遍历。

3.2. BFS实现

让我们实现bfs()函数，并将其逐行与我们之前学习的理论联系起来：

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算法的实际实现，将我们讨论的理论概念转化为可操作的Kotlin代码。其核心是使用队列逐层探索节点，确保系统化的访问模式，符合BFS范式。

过程首先将起始节点标记为已访问，然后迭代地探索每个节点的邻居，以最宽泛的方式遍历图。这种方法保证了从起始点可达的所有节点都被访问，一次一层。

3.3. 理解BFS实现

在观察了BFS算法的运行之后，让我们深入到我们实现的具体细节：

**初始化：**我们首先创建一个名为_visited_的可变集合，用于跟踪我们已访问过的节点。这很重要，以防止重新访问节点，这可能导致循环图中的无限循环。我们还创建了一个名为_queue_的队列来管理需要探索的节点。这个队列将确保我们按照发现的顺序探索节点，符合BFS策略。
**起始节点：**BFS算法通过将起始节点添加到队列来开始。这是我们进入图的入口点。
**遍历循环：**BFS实现的核心是一个循环，只要队列中还有待探索的节点，这个循环就会运行。在这个循环内部，我们从队列中移除下一个要探索的节点（vertex），并检查我们是否访问过它。如果没有，我们通过将其包含在_visited_集合中将其标记为已访问。
**探索邻居：**对于每个未访问的节点，我们从图中检索其邻居。然后我们过滤掉已经访问过的邻居，并将其余的添加到队列中。这一步确保了我们将最终探索从起始节点可达的每个节点，按照从近到远的顺序。
**完成：**一旦队列为空，表示没有更多的节点要探索，循环就会终止。此时，_visited_集合包含了在遍历过程中访问的所有节点，按照它们被访问的顺序。然后这个集合作为BFS实现的结果返回。

4. 测试我们的BFS实现

最后，为了确保我们的BFS按预期工作，我们需要测试我们的实现。让我们通过编写一个JUnit测试来验证我们的代码是否正确。使用我们最初定义的图，我们将使用我们的BFS实现来遍历它，并断言我们访问节点的顺序：

@Test
fun `test BFS traversal order`() {
    val graph = mapOf(
        1 to listOf(2, 3, 4),
        2 to listOf(5, 6),
        6 to listOf(),
        3 to listOf(),
        4 to listOf(7, 8),
        5 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)
}

这个测试证明了我们的BFS实现正确地按正确的顺序从根节点遍历了图。在调用我们的bfs()函数以获取遍历顺序后，我们将traversalOrder列表切片以隔离图中的每个层级。最后，使用断言，我们检查每个层级的节点是否符合预期，强调算法的广度优先方法。

5. 结论

在Kotlin中实现BFS算法为有效探索图和树提供了一种很好的方式。通过利用Kotlin的简洁语法和强大的标准库，开发人员可以实施并应用BFS来解决学术和实际应用中的广泛问题。

如常，本文中使用的代码可以在GitHub上找到。