带用户输入的C++无权图BFS最短路径代码问题求助

问题描述 #

• GCC编译后，main函数中的边输入for循环仅执行一次就终止程序
• Clang编译可运行，但输入测试用例（3个顶点、3条边：1-3、1-2、2-3）时，偶尔会随机返回"Given source and destination are not connected"，正确结果应为路径长度1

问题根源 #

1. 非标准变长数组(VLA)的使用
   C++标准不支持vector<int> adjList[numOfVertices]这种栈上的变长数组。GCC对VLA的实现存在兼容性问题，直接导致内存异常触发程序终止；Clang虽支持VLA，但动态栈数组容易引发越界，破坏内存结构，导致随机错误。

2. 顶点索引越界
   代码中顶点编号从1开始，但数组下标是0-based。比如顶点数为3时，adjList[3]会访问数组第4个元素（下标3），而数组实际大小只有3（下标0-2），直接触发数组越界，破坏栈内存，这就是Clang下偶发错误的原因。

3. 缺失必要头文件
   使用INT_MAX但未包含<climits>头文件，使用EXIT_FAILURE但未包含<cstdlib>，属于未定义行为，部分编译器会报错或出现异常。

4. 非法输入处理不规范
   输入非法边时直接返回EXIT_FAILURE，既无错误提示，也未释放已分配的内存，存在内存泄漏风险。

修复后的代码 #

#include <iostream>
#include <vector>
#include <list>
#include <climits>
#include <cstdlib>

using namespace std;

bool BFS(vector<int> adjList[], int source, int dest, int numOfVertices, int pred[], int dist[]);
void printShortestDistance(vector<int> adjList[], int s, int dest, int numOfVertices);

int main()
{
    int numOfVertices, numOfEdges;
    cin >> numOfVertices >> numOfEdges;

    // 动态分配数组，适配1-based顶点编号，避免变长数组问题
    vector<int>* adjList = new vector<int>[numOfVertices + 1];

    if (2 <= numOfVertices && numOfVertices <= 100000 && 1 <= numOfEdges && numOfEdges <= 100000)
    {
        for (int i = 0; i < numOfEdges; i++)
        {
            int node1, node2;
            cin >> node1 >> node2;

            if ((1 <= node1) && (1 <= node2) && (node1 <= numOfVertices) && (node2 <= numOfVertices) && (node1 != node2))
            {
                adjList[node1].push_back(node2);
                adjList[node2].push_back(node1);
            }
            else{
                cerr << "输入的边不合法！" << endl;
                delete[] adjList;
                return EXIT_FAILURE;
            }
        }

        int source = 1;
        int dest = numOfVertices;
        printShortestDistance(adjList, source, dest, numOfVertices);
    }
    else{
        cerr << "顶点数或边数超出范围！" << endl;
        delete[] adjList;
        return EXIT_FAILURE;
    }

    delete[] adjList;
    return 0;
}

void printShortestDistance(vector<int> adjList[], int source, int dest, int numOfVertices)
{
    // 动态分配pred和dist数组，避免栈溢出
    int* pred = new int[numOfVertices + 1];
    int* dist = new int[numOfVertices + 1];

    if (!BFS(adjList, source, dest, numOfVertices, pred, dist))
    {
        cout << "给定的起点和终点不连通";
        delete[] pred;
        delete[] dist;
        return;
    }

    vector<int> path;
    int crawl = dest;
    path.push_back(crawl);
    while (pred[crawl] != -1)
    {
        path.push_back(pred[crawl]);
        crawl = pred[crawl];
    }

    cout << "最短路径长度为 : " << dist[dest];

    cout << "\n路径为::\n";
    for (int i = path.size() - 1; i >= 0; i--)
        cout << path[i] << " ";

    delete[] pred;
    delete[] dist;
}

bool BFS(vector<int> adjList[], int source, int dest, int numOfVertices, int pred[], int dist[])
{
    list<int> queue;
    bool* visited = new bool[numOfVertices + 1];

    // 从1开始遍历顶点，适配1-based编号
    for (int i = 1; i <= numOfVertices; i++)
    {
        visited[i] = false;
        dist[i] = INT_MAX;
        pred[i] = -1;
    }

    visited[source] = true;
    dist[source] = 0;
    queue.push_back(source);

    while (!queue.empty())
    {
        int u = queue.front();
        queue.pop_front();

        // 范围for循环简化遍历
        for (int v : adjList[u])
        {
            if (!visited[v])
            {
                visited[v] = true;
                dist[v] = dist[u] + 1;
                pred[v] = u;
                queue.push_back(v);

                if (v == dest)
                {
                    delete[] visited;
                    return true;
                }
            }
        }
    }

    delete[] visited;
    return false;
}

核心修复点 #

• 用动态分配数组替代栈上变长数组，符合C++标准，彻底解决内存异常问题
• 将数组大小设为numOfVertices + 1，适配1-based顶点编号，避免索引越界
• 补充必要头文件，确保所有常量和函数可正常使用
• 非法输入时增加中文提示，并释放内存，避免泄漏
• BFS中用范围for循环简化代码，找到目标后及时释放内存

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