Kotlin中BFS实现图最短路径遇返回逻辑问题，求修复帮助

一、核心错误分析 #

1. 图构建函数（buildGraph3）逻辑问题 #

• 内层循环冗余：每条边被重复处理两次（for (n in 0 until edges[i].size)会循环两次，重复执行边添加操作），导致邻接列表出现重复节点。
• 无向边处理错误：graph[b]?.add(b)是错误逻辑，无向图中节点b应添加节点a作为邻接节点，而非自身。

2. BFS队列处理逻辑问题 #

• 队列元素操作破坏结构：直接修改队列头部的列表（queue[0].removeFirst()、queue[0].removeAt(1)）会打乱队列的正常顺序，且当列表仅剩一个元素时removeAt(1)会抛出索引越界异常。
• 队列元素取出方式错误：未正确取出完整的「节点-距离」配对，而是直接操作队列头部的列表元素，导致后续逻辑混乱。
• 循环结束后返回逻辑无效：queue.sortedByDescending { it.size }和return queue[0][1]不符合BFS终止逻辑，若循环结束说明未找到路径，应返回明确的无效标识（如-1）。

二、修正后的代码 #

1. 正确的图构建函数 #

fun buildGraph(edges: List<List<Char>>): HashMap<Char, MutableList<Char>> {
    val graph = HashMap<Char, MutableList<Char>>()
    for (edge in edges) {
        val a = edge[0]
        val b = edge[1]
        // 初始化节点的邻接列表
        if (!graph.containsKey(a)) graph[a] = mutableListOf()
        if (!graph.containsKey(b)) graph[b] = mutableListOf()
        // 无向图双向添加邻接关系
        graph[a]?.add(b)
        graph[b]?.add(a)
    }
    return graph
}

2. 修正后的BFS最短路径函数 #

fun shortestPath(edges: List<List<Char>>, root: Char, destination: Char): Int {
    val graph = buildGraph(edges)
    val visited = hashSetOf(root)
    // 使用Pair存储节点与距离，逻辑更清晰，避免列表操作错误
    val queue = ArrayDeque<Pair<Char, Int>>()
    queue.add(Pair(root, 0))

    while (queue.isNotEmpty()) {
        // 取出队列头部的节点和对应距离
        val (currentNode, currentDistance) = queue.removeFirst()
        
        // 找到目标节点，直接返回当前距离
        if (currentNode == destination) return currentDistance

        // 遍历邻接节点，未访问则加入队列
        graph[currentNode]?.forEach { neighbor ->
            if (!visited.contains(neighbor)) {
                visited.add(neighbor)
                queue.add(Pair(neighbor, currentDistance + 1))
            }
        }
    }

    // 未找到路径时返回-1（可根据需求调整返回值）
    return -1
}

三、测试验证 #

使用你提供的输入测试：

val SPE = listOf(
    listOf('w', 'x'),
    listOf('x', 'y'),
    listOf('z', 'y'),
    listOf('z', 'v'),
    listOf('w', 'v')
)
// w到z的最短路径为2（w->v->z）
println(shortestPath(SPE, 'w', 'z')) // 输出：2

内容的提问来源于stack exchange，提问作者OEThe11