我的广度优先搜索算法有什么问题，它因分段错误而崩溃？

Question

当我运行我的代码时，它抛出一个分段错误，我已经尝试重写代码几次。仍然无济于事，它甚至不会运行。我的程序一启动就发生分段错误。它应该做的是使用 Linux 中的 ncurses 库从给定的坐标在屏幕上打印一条路径。这是有问题的片段，其中包含 gdb 表示分段错误的行，它（片段）也重现了问题。

编辑：这将有助于解释我正在尝试做什么，但使用的是动态数组。 Breadth First Search

编辑 2：变量 frontier 应该跟踪特定索引处的 X 和 Y 值。 add_neighbors 函数用于将所有四个邻居（假设它们尚未添加）添加到边界和 came_from 数组。

frontier[index][0]是X值。
frontier[index][1] 是 Y 值。

在第一个 while 循环之前，我设置了起始位置 x1 和 y1。在第一个 while 循环中，它递增从边界获取新坐标，然后处理并添加到 came_from 数组。

例如：
(x1,y1) (x1+1,y1)
(x1,y1+1) (x1+1,y1+1)
(x1,y2) (x2,y2)

我正在尝试从 (x1,y1) 到 (x2,y2)。当然希望能更好地解释它。我要实现的是广度优先搜索 (BFS) 算法。使用两个数组，一个是 frontier（跟踪访问过的位置）和 came_from（跟踪 X 和 Y 从 x1,y1 到 x2,y2 的路径）。更新了代码以反映第一个答案。另外添加了一条评论来解释错误可能在哪里，不太确定，但我一直在调试它。看起来 came_from 数组从未设置为 x 和 y。

代码：

/*
 * pathfind.c - Simple Breadth First Search algorithm implementation.
 *
 * Author: Philip R. Simonson
 * Date  : 05/17/2021
 *
 ****************************************************************************
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <ncurses.h>
    
#define MAXHEIGHT 24
#define MAXWIDTH 80

/* Add neighboring positions to the arrays.
 */
int add_neighbors(int **frontier, int ***came_from, int count, int x, int y)
{
    // North
    if(y > 0 && came_from[y - 1][x][0] < 0) {
        frontier[count][0] = x;
        frontier[count][1] = y;
        count++;
        came_from[y - 1][x][0] = x;
        came_from[y - 1][x][1] = y;
    }
    // South
    if(y < MAXHEIGHT-1 && came_from[y + 1][x][0] < 0) {
        frontier[count][0] = x;
        frontier[count][1] = y;
        count++;
        came_from[y + 1][x][0] = x;
        came_from[y + 1][x][1] = y;
    }
    // West
    if(x > 0 && came_from[y][x - 1][0] < 0) {
        frontier[count][0] = x;
        frontier[count][1] = y;
        count++;
        came_from[y][x - 1][0] = x;
        came_from[y][x - 1][1] = y;
    }
    // East
    if(x < MAXWIDTH-1 && came_from[y][x + 1][0] < 0) {
        frontier[count][0] = x;
        frontier[count][1] = y;
        count++;
        came_from[y][x + 1][0] = x;
        came_from[y][x + 1][1] = y;
    }
    return count; // Return counter for frontier
}
/* Simple BFS algorithm for path finding.
 */
void path_finding(int x1, int y1, int x2, int y2)
{
    int **frontier, ***came_from;
    int index, count;
    int i, j;

    index = 0;
    count = 0;

    // Initialise frontier array
    frontier = malloc(sizeof(int *) * MAXHEIGHT * MAXWIDTH);
    for(i = 0; i < (MAXHEIGHT * MAXWIDTH); i++) {
        frontier[i] = malloc(sizeof(int) * 2);
    }

    // Create came_from array
    came_from = malloc(sizeof(int **) * MAXHEIGHT);
    for(i = 0; i < MAXHEIGHT; i++) {
        came_from[i] = malloc(sizeof(int *) * MAXWIDTH);
        for(j = 0; j < MAXWIDTH; j++) {
            came_from[i][j] = malloc(sizeof(int) * 2);
            came_from[i][j][0] = -1;
            came_from[i][j][1] = -1;
        }
    }

    // Add start to came_from
    came_from[y1][x1][0] = -9;
    came_from[y1][x1][1] = -9;

    // Add start to frontier
    frontier[count][0] = x1;
    frontier[count][1] = y1;
    count++;

    while(index < count) {
        int x = frontier[index][0];
        int y = frontier[index][1];
        index++;

        if(x == x2 && y == y2)
            break;

        count = add_neighbors(frontier, came_from, count, x, y);
    }

    // Set temp position variables to end position
    {
        int x = x2;
        int y = y2;

        while(x != x1 || y != y1) {
            int tempy = y;
            mvprintw(y, x, "*");
            // Segmentation fault because came_from[tempy][x][1] and came_from[tempy][x][0]
            // always equals -1 which is out of bounds. Not sure how to fix it, something
            // is wrong with add_neighbors function I think.
            y = came_from[tempy][x][1];
            x = came_from[tempy][x][0];
        }
    }

    // TODO: Return came_from array!

    // Free all resources from both arrays
    for(i = 0; i < MAXHEIGHT; i++) {
        for(j = 0; j < MAXWIDTH; j++) {
            free(came_from[i][j]);
        }
        free(came_from[i]);
    }
    free(came_from);
    for(i = 0; i < (MAXHEIGHT * MAXWIDTH); i++) {
        free(frontier[i]);
    }
    free(frontier);
}

int main(void)
{
    initscr();
    noecho();
    clear();

    path_finding(0, 2, 7, 8);

    refresh();
    getch();
    endwin();
    return 0;
}

编译：cc -o test test.c -lncurses

GDB 输出：

[philip@darkstar temp]$ gdb --batch --ex r --ex bt --ex q temp

Program received signal SIGSEGV, Segmentation fault.
                                                    0x000055555555599d in path_finding (x1=0, y1=2, x2=7, y2=8) at src/pathfind.c:117
117             y = came_from[tempy][x][1];
#0  0x000055555555599d in path_finding (x1=0, y1=2, x2=7, y2=8) at src/pathfind.c:117
#1  0x00005555555551ff in main () at src/main.c:11
A debugging session is active.

    Inferior 1 [process 65294] will be killed.

Quit anyway? (y or n) [answered Y; input not from terminal]
[philip@darkstar temp]$

Answer 1

部分分配大小不正确：

frontier = malloc(sizeof(frontier) * MAXHEIGHT * MAXWIDTH);应该是
```
frontier = malloc(sizeof(*frontier) * MAXHEIGHT * MAXWIDTH);
```
frontier[i] = malloc(sizeof(*frontier) * 2); 应为：
```
frontier[i] = malloc(sizeof(frontier[i][0]) * 2);
```

这些访问没有得到适当的保护：

if(y <= MAXHEIGHT && came_from[y + 1][x][0] < 0)应该是
```
 if (y < MAXHEIGHT-1 && came_from[y + 1][x][0] < 0)
```
if(x <= MAXWIDTH && came_from[y][x + 1][0] < 0)应该是
```
 if(x < MAXWIDTH-1 && came_from[y][x + 1][0] < 0)
```
frontier 数组未初始化。您应该使用 calloc() 将 int 数组初始化为 0 或运行初始化循环。
在 while (x != x1 || y != y1) 循环中，当您读取 y = came_from[tempy][x][1] 时，您不会检查 y >= 0。由于您初始化了 came_from[y1][x1][0] = -9; 它是负数并在您设置 tempy = y.
的下一次迭代期间导致越界访问
从代码中看算法不是很明显，为了reader，您可能想多加评论。

我的广度优先搜索算法有什么问题，它因分段错误而崩溃？

What is wrong with my breadth first search algorithm, it crashes with a segmentation fault?

c

breadth-first-search

segmentation-fault