基于BFS算法的无向图顶点最短距离函数SD()实现错误排查求助

我看了你的代码，发现几个关键问题导致了最短距离计算错误，尤其是你提到的测试场景中正确输出2却得到1的情况，主要是距离更新逻辑错误，还有一些其他需要完善的地方，下面逐一说明：

主要错误点 #

1. 距离更新逻辑完全错误 #

在SD函数中，你更新邻居节点距离的代码是：

distance[i] = distance[i] + 3;

这完全不符合BFS的最短距离计算规则。BFS中，每个邻居节点的距离应该是当前节点的距离加1（因为每走一条边距离加1）。正确的写法应该是：

distance[i] = distance[w-1] + 1;

这里w是当前出队的1-based顶点，w-1是它在distance数组中的0-based索引，邻居i的距离就是当前节点距离加1。

2. 初始距离设置不够直观 #

你初始化起点距离的代码是：

distance[v-1] = distance[v-1] + 1;

虽然因为初始distance[v-1]是-1，加1后得到0（正确的起点距离），但这种写法很容易混淆，直接赋值为0更清晰：

distance[v-1] = 0;

3. 未独立管理访问标记 #

你的代码直接使用了Graph结构体中的visited数组，这会导致如果多次调用SD函数，之前的访问状态会残留。正确的做法是在SD函数内部创建自己的访问标记数组，避免影响原Graph的状态，也保证每次调用都是全新的初始化。

4. 未处理起点和终点相同的情况 #

虽然题目中可能没覆盖这种场景，但严谨来说，如果v == w，应该直接返回0，不需要走BFS流程。

修正后的SD函数代码 #

int SD(Graph g, int v, int z){
    // 处理起点和终点相同的情况
    if (v == z) {
        return 0;
    }

    int *distance = (int *)malloc(sizeof(int) * g.V);
    int *visited = (int *)malloc(sizeof(int) * g.V); // 内部管理访问标记
    if (!distance || !visited) {
        // 内存分配失败处理
        if (distance) free(distance);
        if (visited) free(visited);
        return -1;
    }

    // 初始化距离和访问标记
    for(int i = 0; i < g.V; i++) {
        distance[i] = -1;
        visited[i] = 0;
    }

    Queue q;
    q.size = 0;
    q.head = NULL;
    q.tail = NULL;

    int w;
    int i;

    enqueue(&q, v);
    distance[v-1] = 0; // 直接设为0，清晰明了
    visited[v-1] = 1;

    while(isEmptyQueue(q) == 0) {
        w = dequeue(&q);
        for(i = 0; i < g.V; i++) {
            if(g.matrix[w-1][i] == 1 && visited[i] == 0) {
                visited[i] = 1;
                distance[i] = distance[w-1] + 1; // 正确的距离更新逻辑

                // 如果找到终点，可以提前退出，优化性能
                if ((i+1) == z) {
                    removeAllItemsFromQueue(&q); // 清理队列
                    break;
                }

                enqueue(&q, i+1);
            }
        }
    }

    int result = (z > 0 && z <= g.V) ? distance[z-1] : -1;

    // 释放内存，避免泄漏
    free(distance);
    free(visited);

    return result;
}

其他需要注意的点 #

• 我添加了内存分配失败的处理，避免程序崩溃；
• 当找到终点时提前退出BFS，优化了性能；
• 释放了SD函数内部分配的内存，避免内存泄漏；
• 使用独立的visited数组，不会影响原Graph的状态，保证每次调用SD都是独立的计算。

现在你可以测试之前的场景，比如假设测试用例是顶点1到顶点3，路径是1-2-3，修正后的代码应该会正确返回2。

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