How do I trace back the shortest path found using BFS

See more:

C#

.NET

algorithm

search

So I've implemented a BFS search algorithm to find the shortest path from the first index in the binary matrix (top left) to the last index (bottom right).

I would now like to trace back the path that I found, but I have no idea how to keep track of the parent node and when to actually add it to a data structure.

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;
}

What I have tried:

I've tried keeping track of the parent node but I kept getting every other node as well. So I'm not sure how to.