I'm trying to code BFS algorithm in C++ for finding a cell in a grid , however the code is not giving any output (just blank ) . The code is similar to all standard codes given online but I am unable to understand how it is not working .
class grid graph is the class to declare the graph , which is a 2d array , with 0 as path and 1 as obstacle
pathfinder is a method to find the path , using breadth first search algorithm and it has its own helper function add neighbours to add neighbours
#include<iostream>
#include <bits/stdc++.h>
using namespace std ;
class grid_graph{
public:
vector<vector<int>> A;
grid_graph(vector<vector<int>> a){
A = a;
}
int N_rows = A.size();
int N_cols = A[0].size();
void pathfinder(int src_r,int src_c,int dest_r,int dest_c);
void neighbour_adder(int r,int c,queue<int>& R,queue<int>& C,vector<vector<bool>>& visited);//bool visited[][N_cols]
};
void grid_graph::pathfinder(int src_r,int src_c,int dest_r,int dest_c){
queue<int> R;
queue<int> C;
R.push(src_r);
C.push(src_c);
// bool visited[N_rows][N_cols]{};
vector<vector<bool>> visited;
for(int i=0; i<N_rows; i++){
for(int j=0; j<N_cols; j++){
visited[i][j]=false;
}
}
// visited[src_r][src_c] = true;
while(!R.empty()){
cout<<R.front()<<" "<<C.front()<<endl;
if(R.front()==dest_r && C.front()==dest_c){
cout<<"reached"<<endl;
}
visited[R.front()][C.front()]=true;
neighbour_adder(R.front(),C.front(),R,C,visited);
R.pop();
C.pop();
}
}
void grid_graph::neighbour_adder(int r,int c,queue<int>& R,queue<int>& C,vector<vector<bool>>& visited){//bool visited[][N_cols]
// assuming only up down left right motion possible
int d1[4] = {0,0,+1,-1};
int d2[4] = {+1,-1,0,0};
for(int i=0; i<4; i++){
int r_next = r + d1[i];
int c_next = c + d2[i];
if(r_next<0 || c_next<0 || r_next>=N_rows || c_next>=N_cols){
continue;
}
// I have taken 1 as obstacle 0 as not obstacle
if(A[r_next][c_next]==1 || visited[r_next][c_next]==true){
continue;
}
R.push(r_next);
C.push(c_next);
}
}
int main(){
grid_graph g2( {{ 0, 0, 0 },
{ 0, 1, 0 },
{ 0, 0, 0 } });
g2.pathfinder(0,0,2,2);
return 0;
}
EDIT 1 : The code now perfectly works thanks to the solution , here is the working code for anyone else who needs it :
/
/////////////////////////////////////////////////
class grid_graph{
public:
vector<vector<int>> A;
// grid_graph(vector<vector<int>> a){
// A = a;
// }
// int N_rows = A.size();
// int N_cols = A[0].size();
/////////////////////////////////////////////////////////////// from SO
grid_graph(vector<vector<int>> a): A( a ){}
int colCount() const
{
return A[0].size();
}
int rowCount() const
{
return A.size();
}
////////////////////////////////////////////////////////////
void pathfinder(int src_r,int src_c,int dest_r,int dest_c);
void neighbour_adder(int r,int c,queue<int>& R,queue<int>& C,vector<vector<bool>>& visited);//bool visited[][N_cols]
};
void grid_graph::pathfinder(int src_r,int src_c,int dest_r,int dest_c){
queue<int> R;
queue<int> C;
R.push(src_r);
C.push(src_c);
// bool visited[N_rows][N_cols]{};
// vector<vector<bool>> visited;
// for(int i=0; i<N_rows; i++){
// for(int j=0; j<N_cols; j++){
// visited[i][j]=false;
// }
// }
int N_rows = rowCount();
int N_cols = colCount();
///////////////////////////////////from stackexchange
vector<vector<bool> > visited(N_rows,vector<bool>(N_cols, false));
/////////////////////////////////
// visited[src_r][src_c] = true;
while(!R.empty()){
if(R.front()==dest_r && C.front()==dest_c){
cout<<"reached"<<endl;
}
visited[R.front()][C.front()]=true;
neighbour_adder(R.front(),C.front(),R,C,visited);
R.pop();
C.pop();
}
}
void grid_graph::neighbour_adder(int r,int c,queue<int>& R,queue<int>& C,vector<vector<bool>>& visited){//bool visited[][N_cols]
// assuming only up down left right motion possible
int d1[4] = {0,0,+1,-1};
int d2[4] = {+1,-1,0,0};
int N_rows = rowCount();
int N_cols = colCount();
for(int i=0; i<4; i++){
int r_next = r + d1[i];
int c_next = c + d2[i];
if(r_next<0 || c_next<0 || r_next>=N_rows || c_next>=N_cols){
continue;
}
// I have taken 1 as obstacle 0 as not obstacle
if(A[r_next][c_next]==1 || visited[r_next][c_next]==true){
continue;
}
R.push(r_next);
C.push(c_next);
}
}
/////////////////////////////////////////////////////////////////////////////////////////////////
/* Dijkstra algorithm is a greedy algorithm used for shortest path in non negative weighted
graphs . we have lazy , eager , d ary heap and fibonacci heap versions of it .
*/
/*Topological sort , topsort done using dfs over all unvisited nodes and putting them in reverse
in an array (which is the topsort output ) , can only be done over directed acyclic graph DAG*/
int main(){
// cout<<"hello world"<<endl;
unweighted_graph g1;
/////////////////////////////////////
// g1.addedge_undirected(1,2);
// g1.addedge_directed(2,3);
// g1.print_graph();
// print graph , directed and undirected edges functions are working properly
////////////////////////////////////
////////////////////////////////////
// graph taken from https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/
// g1.addedge_directed(0, 1);
// g1.addedge_directed(0, 2);
// g1.addedge_directed(1, 2);
// g1.addedge_directed(2, 0);
// g1.addedge_directed(2, 3);
// g1.addedge_directed(3, 3);
// g1.BFS_iterative(2);
// gave output 2 0 3 1 which is correct hence iterative BFS is working properly
// g1.BFS_recursive(2);
// gave output 2 0 3 1 which is correct hence recursive BFS is working correctly
////////////////////////////////////
// g.addedge_directed(0, 1);
// g.addedge_directed(0, 2);
// g.addedge_directed(1, 2);
// g.addedge_directed(2, 0);
// g.addedge_directed(2, 3);
// g.addedge_directed(3, 3);
// g.DFS_iterative(0);
// gave output 2 3 0 1 for 2 , 3 for 3 , 0 2 3 1 for 0 hence it is working
// g.DFS_recursive(0);
// gave output 2 0 1 3 for 2 , 3 for 3 , 0 1 2 3 for 0 hence it is working
////////////////////////////////////
grid_graph g2( {{ 0, 0, 0 },
{ 0, 1, 0 },
{ 0, 0, 0 } });
g2.pathfinder(0,0,2,2);
return 0;
}
My VS Code is showing bits/std.h not found error , and I have no idea where the libraries are on my pc and how to source , so can anyone help in it too
EDIT 2 - Code is now availaible at github along with code for BFS DFS Dijkstra at https://github.com/ayush-agarwal-0502/Graph-Algorithms-
This is incorrect.
// bool visited[N_rows][N_cols]{};
vector<vector<bool>> visited;
for(int i=0; i<N_rows; i++){
for(int j=0; j<N_cols; j++){
visited[i][j]=false;
}
}
Here is the correct code to initialize a 2D vector of a specified size.
vector<vector<bool> > visited(
N_rows,
vector<bool>(N_cols, false));
This is questionable
grid_graph(vector<vector<int>> a){
A = a;
}
int N_rows = A.size();
int N_cols = A[0].size();
I would write:
grid_graph(vector<vector<int>> a)
: A( a )
{}
int colCount() const
{
return A[0].size();
}
int rowCount() const
{
return A.size();
}