如何在二进制矩阵中使用BFS算法回溯最短路径

我已经实现了BFS算法，能成功计算从左上角到右下角的最短步数。我的二进制矩阵中，0代表可通行，1代表不可通行。目前用Visited网格把已访问节点标记为2，但只能看到哪些节点被访问过，没法还原出实际的最短路径。

比如下面这个网格：

int[][] grid = new[]
{
    new int[] { 0, 0, 0, 0},
    new int[] { 1, 1, 0, 0},
    new int[] { 1, 0, 0, 0},
    new int[] { 1, 1, 0, 0}
};

这里有两条最短路径，步数都是5，我的代码能输出步数，但我需要输出具体路径，比如其中一条是0,0 - 0,1 - 1,2 - 2,2 - 3,3。我知道应该记录每个节点的父节点来回溯路径，但不知道具体怎么实现。以下是我的现有代码：

int[][] dirs = new[]
{
    new[] { 0, 1 }, //Bottom
    new[] { 1, 1 }, //Bottom right
    new[] { 1, 0 }, //Right
    new[] { 1, -1 }, //Top right
    new[] { 0, -1 }, //Top
    new[] { -1, -1 }, //Top left
    new[] { -1, 0 }, //Left
    new[] { -1, 1 } //Bottom left
};

public int BinaryMatrix(int[][] grid)
{
    /* Length of the rows */
    var rowLength = grid.Length;

    /* The length of each col */
    var colLength = grid[0].Length;

    /* Can't find a path */
    if (grid[0][0] == 1 || grid[rowLength - 1][colLength - 1] == 1)
        return -1;

    var Queue = new Queue<int[]>(); /* Coordinates */

    /* Make a copy of the grid on order to update and perform checks without manipulating the original one. */
    int[][] visited = new int[rowLength][];
    for (int i = 0; i < visited.Length; i++)
        visited[i] = new int[colLength];

    Queue.Enqueue(new[] { 0, 0 });
    visited[0][0] = 2;
    int steps = 1;

    while (Queue.Count != 0)
    {
        int levelSize = Queue.Count;
        for (int r = 0; r < levelSize; r++)
        {
            int[] coord = Queue.Dequeue();

            var cy = coord[0]; /* Y */
            var cx = coord[1]; /* X */

            /* If what we just popped has the same coordinates as the destination */
            if (cy == rowLength - 1 && cx == colLength - 1)
            {
                /* Traceback */
                return steps;
            }

            for (int i = 0; i < dirs.Length; i++)
            {
                int neighborY = dirs[i][0] + cy;
                int neighborX = dirs[i][1] + cx;
                
                /* Bounds check */
                if (neighborX >= 0 && neighborX < colLength && neighborY >= 0 && neighborY < rowLength)
                {
                    /* Visited check */
                    if (visited[neighborY][neighborX] == 0 && grid[neighborY][neighborX] == 0)
                    {
                        Queue.Enqueue(new[] { neighborY, neighborX });
                        visited[neighborY][neighborX] = 2;
                    }
                }
            }
        }
        
        /* Increment once we're done traversing through a level */
        steps++;
    }
    return -1;
}

要还原最短路径，核心是给每个节点记录它的父节点坐标——也就是从哪个节点走到当前节点的。具体实现步骤如下：

1. 新增父节点存储结构：创建一个和网格尺寸一致的三维数组parent，每个元素存储对应节点的父节点坐标（[父Y, 父X]），初始为null表示未设置。
2. 入队时记录父节点：当发现可通行的未访问邻居时，除了标记已访问和入队，还要把当前节点设为该邻居的父节点。
3. 终点回溯生成路径：到达终点后，从终点开始沿着parent数组倒推回起点，再反转列表得到正向路径。

修改后的完整代码 #

int[][] dirs = new[]
{
    new[] { 0, 1 }, //下
    new[] { 1, 1 }, //右下
    new[] { 1, 0 }, //右
    new[] { 1, -1 }, //右上
    new[] { 0, -1 }, //上
    new[] { -1, -1 }, //左上
    new[] { -1, 0 }, //左
    new[] { -1, 1 } //左下
};

// 返回包含步数和路径的元组，同时兼容原功能
public (int steps, string path) BinaryMatrixWithPath(int[][] grid)
{
    var rowLength = grid.Length;
    var colLength = grid[0].Length;

    // 起点或终点不可通行，直接返回无路径
    if (grid[0][0] == 1 || grid[rowLength - 1][colLength - 1] == 1)
        return (-1, "无有效路径");

    var queue = new Queue<int[]>();
    int[][] visited = new int[rowLength][];
    // 父节点数组：每个位置存储[父Y, 父X]，初始为null
    int[][][] parent = new int[rowLength][][];
    
    // 初始化visited和parent数组
    for (int i = 0; i < rowLength; i++)
    {
        visited[i] = new int[colLength];
        parent[i] = new int[colLength][];
    }

    queue.Enqueue(new[] { 0, 0 });
    visited[0][0] = 2;
    int steps = 1;
    bool foundPath = false;
    int[] endCoord = new[] { rowLength - 1, colLength - 1 };

    while (queue.Count != 0)
    {
        int levelSize = queue.Count;
        for (int r = 0; r < levelSize; r++)
        {
            int[] coord = queue.Dequeue();
            var cy = coord[0];
            var cx = coord[1];

            // 到达终点，标记并退出循环
            if (cy == endCoord[0] && cx == endCoord[1])
            {
                foundPath = true;
                break;
            }

            // 遍历所有方向的邻居
            for (int i = 0; i < dirs.Length; i++)
            {
                int neighborY = dirs[i][0] + cy;
                int neighborX = dirs[i][1] + cx;
                
                // 边界检查 + 可通行 + 未访问
                if (neighborX >= 0 && neighborX < colLength && neighborY >= 0 && neighborY < rowLength)
                {
                    if (visited[neighborY][neighborX] == 0 && grid[neighborY][neighborX] == 0)
                    {
                        queue.Enqueue(new[] { neighborY, neighborX });
                        visited[neighborY][neighborX] = 2;
                        // 记录当前节点为邻居的父节点
                        parent[neighborY][neighborX] = new[] { cy, cx };
                    }
                }
            }
        }
        if (foundPath)
            break;
        steps++;
    }

    // 未找到路径
    if (!foundPath)
        return (-1, "无有效路径");

    // 回溯生成路径：从终点倒推到起点
    List<string> pathList = new List<string>();
    int[] current = endCoord;
    while (current != null)
    {
        pathList.Add($"{current[0]},{current[1]}");
        current = parent[current[0]][current[1]];
    }
    // 反转得到从起点到终点的正向路径
    pathList.Reverse();
    string path = string.Join(" - ", pathList);

    return (steps, path);
}

代码说明 #

• 父节点数组：parent数组负责记录每个节点的来源，确保回溯时能准确找到上一步的位置。
• 路径回溯：从终点开始，不断获取父节点直到起点，反转后就是完整的正向路径。
• 返回值：用元组同时返回步数和路径字符串，兼顾原有的步数计算需求和新的路径输出需求。

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