基于BFS算法的C语言最短路径程序启动节点异常崩溃排查

核心问题：内存越界访问 #

返回值3221225477是Windows平台下的内存访问违规（STATUS_ACCESS_VIOLATION），根源在于代码使用0-based索引存储图数据，但输入的顶点编号是1-based的。当输入顶点编号等于node（比如测试用例中的5）时，访问g->adjList[5]会超出数组合法索引范围（数组仅分配了0~4的空间），触发内存错误。

比如测试输入中的边5 3，调用addEdge(g,5,3)时，g->adjList[5]属于越界访问，直接破坏内存结构，导致后续程序崩溃。

修复方案 #

推荐采用第二种方式，更贴合输入习惯：

方式1：将输入顶点转换为0-based #

在读取边的src和dest后，统一减1，把1-based编号转为0-based：

for (i = 0; i < edge; i++) {
    int src, dest;
    scanf("%d %d", &src, &dest);
    // 转换为0-based索引
    src--;
    dest--;
    addEdge(g, src, dest);
}

同时，启动节点和目标节点INDEX也要同步转换：

// main函数调用bfs前
int startNode = 4;
startNode--;
INDEX--;
printf("shortest distance = %d", bfs(g, startNode));

方式2：将图改为1-based索引存储 #

修改createGraph函数，分配vertices + 1大小的数组，让顶点编号直接对应数组索引，无需修改输入逻辑：

struct graph *createGraph(int vertices) {
    int i;
    struct graph *g = (struct graph *)malloc(sizeof(struct graph));
    g->vertices = vertices;
    // 分配vertices+1个元素，支持1~vertices的索引
    g->adjList = (struct node **)malloc((vertices + 1) * sizeof(struct node *));
    g->visited = (bool *)malloc((vertices + 1) * sizeof(bool));
    g->dist = (int *)malloc((vertices + 1) * sizeof(int));
    // 初始化1~vertices的元素，0索引闲置
    for (i = 1; i <= vertices; i++) {
        g->adjList[i] = NULL;
        g->visited[i] = 0;
        g->dist[i] = -1;
    }
    return g;
}

额外优化点 #

• 把全局变量node, edge, INDEX改为局部变量，避免全局变量的潜在冲突；
• addEdge中处理src == dest的自环边时，会重复添加双向边，可增加判断跳过重复操作；
• 程序结束前释放malloc分配的内存，避免内存泄漏。

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