Kotlin最短路径算法报错求助：IndexOutOfBoundsException异常排查

异常信息 #

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 0 out of bounds for length 0
    at java.base/jdk.internal.util.Preconditions.outOfBounds(Preconditions.java:64)
    at java.base/jdk.internal.util.Preconditions.outOfBoundsCheckIndex(Preconditions.java:70)
    at java.base/jdk.internal.util.Preconditions.checkIndex(Preconditions.java:248)
    at java.base/java.util.Objects.checkIndex(Objects.java:372)
    at java.base/java.util.ArrayList.get(ArrayList.java:459)
    at udacity.GraphPraticeKt.shortestPath(GraphPratice.kt:159)
    at udacity.GraphPraticeKt.main(GraphPratice.kt:264)
    at udacity.GraphPraticeKt.main(GraphPratice.kt)

目标图结构 #

val SPE = listOf(
    listOf('w', 'x'),
    listOf('x', 'y'),
    listOf('z', 'y'),
    listOf('z', 'v'),
    listOf('w', 'v')
)

现有代码 #

fun shortestPath(edges: List<List<Char>>, root: Char, destination: Char): Any {
    val graph =  buildGraph3(edges)
    val visited = hashSetOf(root)
    val queue = mutableListOf(Pair(root, 0))

    while (queue.size > 0){
        val current = queue.removeFirst()
        val node = current.first
        val distance = current.second

        if (node == destination) return distance

        graph[node]!!.forEach{
            if (!visited.contains(it)){
                visited.add(it)
                queue.add(Pair(node, distance + 1))
            }

        }
    }
    queue.sortedByDescending { it.second }

    return println(queue[0].second)
}

fun buildGraph3(edges: List<List<Char>>): HashMap<Char, MutableList<Char>> {
    val graph = HashMap<Char, MutableList<Char>>()

    for (i in edges.indices){
        for (n in 0 until edges[i].size){
            var a = edges[i][0]
            var b = edges[i][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
}

问题分析 #

1. 队列越界异常原因：BFS循环结束后队列已为空，代码仍尝试访问queue[0]，直接触发索引越界异常。同时末尾的排序返回逻辑完全错误，BFS未找到路径时应返回无路径标识，而非操作空队列。
2. BFS核心逻辑错误：添加邻接节点到队列时，错误地将当前节点node而非邻接节点it加入队列，导致永远无法遍历到目标节点z，循环结束后队列为空。
3. 图构建冗余：buildGraph3的内层循环会重复处理每条边两次，虽不影响图结构，但造成不必要的性能损耗。

修复方案 #

1. 修正BFS队列添加逻辑 #

将queue.add(Pair(node, distance + 1))改为queue.add(Pair(it, distance + 1))，确保邻接节点被正确加入队列。

2. 移除错误的末尾逻辑 #

删除queue.sortedByDescending { it.second }及return println(queue[0].second)，替换为返回无路径标识（如-1），同时将函数返回类型从Any改为Int保证类型安全。

3. 优化图构建函数 #

移除buildGraph3的内层循环，每条边仅处理一次，可使用computeIfAbsent简化代码。

修复后完整代码 #

fun shortestPath(edges: List<List<Char>>, root: Char, destination: Char): Int {
    val graph = buildGraph3(edges)
    val visited = hashSetOf(root)
    val queue = mutableListOf(Pair(root, 0))

    while (queue.isNotEmpty()) {
        val (node, distance) = queue.removeFirst()
        
        if (node == destination) return distance

        graph[node]?.forEach { neighbor ->
            if (neighbor !in visited) {
                visited.add(neighbor)
                queue.add(Pair(neighbor, distance + 1))
            }
        }
    }

    // 未找到路径时返回-1
    return -1
}

fun buildGraph3(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]
        graph.computeIfAbsent(a) { mutableListOf() }.add(b)
        graph.computeIfAbsent(b) { mutableListOf() }.add(a)
    }

    return graph
}

验证结果 #

调用shortestPath(SPE, 'w', 'z')将返回预期结果2，且不会触发异常。

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