How to print the predecessor of the nodes while implementing the BFS

Question

this is the code for BFS and it works well we have to find the path from 0,0 to 2,3 (just an example case) but the thing is that the output of this code resembles flood fill algorithm and we dont get the actual predecessors of the nodes

//S->start
//E->end

S 0 0 0
|   
1-1-1-1
|   | |
1 0 1-E
|   | |
1-1-1-1

#include <iostream>
#include <queue>
#include <utility>

//Infinity
#define INF 1000000

using namespace std;

int distances[4][4] = {
  {0,INF,INF,INF},
  {INF,INF,INF,INF},
  {INF,INF,INF,INF},
  {INF,INF,INF,INF},
};
int matrix[4][4] = {
  {1,0,0,0},
  {1,1,1,1},
  {1,0,1,1},
  {1,1,1,1}
};

void BFS()
{
  queue< pair<int,int> > queue;
  //Add the first node
  queue.push(make_pair(0,0));

  while(!queue.empty())
  {
    //cout << "here" << '\n';
    pair<int,int> cur = queue.front();
    queue.pop();
    //Check adjacent nodes
    if(cur.first-1 > 0)
    {
      if((distances[cur.first-1][cur.second] == INF) && (matrix[cur.first-1][cur.second] == 1))
      {
        distances[cur.first-1][cur.second] = distances[cur.first][cur.second]+1;
        queue.push(make_pair(cur.first-1,cur.second));
      }
    }
    if(cur.first+1 < 4)
    {
      if(distances[cur.first+1][cur.second] == INF && (matrix[cur.first+1][cur.second] == 1))
      {
        distances[cur.first+1][cur.second] = distances[cur.first][cur.second]+1;
        queue.push(make_pair(cur.first+1,cur.second));
      }
    }
    if(cur.second-1 > 0)
    {
      if((distances[cur.first][cur.second-1] == INF) && (matrix[cur.first][cur.second-1] == 1))
      {
        distances[cur.first][cur.second-1] = distances[cur.first][cur.second]+1;
        queue.push(make_pair(cur.first,cur.second-1));
      }
    }
    if(cur.second+1 < 4)
    {
      if((distances[cur.first][cur.second+1] == INF) && (matrix[cur.first][cur.second+1] == 1))
      {
        distances[cur.first][cur.second+1] = distances[cur.first][cur.second]+1;
        queue.push(make_pair(cur.first,cur.second+1));
      }
    }
  }

}


int main()
{
  BFS();
  for(int i = 0; i < 4; i++)
  {
    for(int j = 0; j < 4; j++)
    {
      if(distances[i][j] != INF)
        cout << distances[i][j] << ' ';
      else
        cout << "X" << ' ';
    }
    cout << '\n';
  }

  return 0;
}

so basically i want to print the parent of node from (2,3) to (0,0). so can you guys suggest how can i do that.

Answer 1

Here is a java code that stores parents (predecessor) of each node

void bfs(int source){
    List<Integer> nodes = new LinkedList<Integer>();
    int i, element;
    visited[source] = source;
    queue.add(source);
    while(!queue.isEmpty()){
        element = queue.remove();
        i = element;
        nodes.add(element);
        List<Integer> iList = getEdge(i); // returns adjacent nodes
        int x = 0; 
        while(x < iList.size()){ // go through the nodes
            int index = iList.get(x);
            if(visited[index] == -1){ // if they have not been visited
                queue.add(index); // add to queue
                visited[index] = i; // add predecessor 
            }
            x++;
        }
    }
    System.out.println(Arrays.toString(visited));

}

visited = [0, 0, 0, 0, 1, 1, 5, 5, 6, 7]

Answer 2

Create an auxiliary matrix of the same size as the input, and for each point in the matrix, store which was the point from which you visited it. So when you reach the destination, you can traverse the auxiliary matrix from the destination to find the path used.