Home > Mobile >  Grid-graph path finder code using BFS in c
Grid-graph path finder code using BFS in c

Time:06-12

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

CodePudding user response:

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();
}
  • Related