Complete the BFS code to find the path in the maze in C++

//////////////// graph.cpp ////////////////

#include "graph.h" #include

graph::graph() { int vertex; cin >> size; adjList.resize(size,NULL); for(int i = 0; i > vertex; while(vertex != -1) { adjList[i] = new vnode(vertex,adjList[i]); // insert at begining cin >> vertex; } } }

//////////////// graph.h //////////////// #ifndef GRPH #define GRPH

#include #include #include

using namespace std;

struct vnode { int v; // vertex vnode *next; vnode(int u, vnode *n) {v=u; next=n;} };

typedef vnode * vnodeptr;

class graph { public: graph(); // interactive constructor using cin

protected: int size; vector adjList; };

#endif

//////////////// maze.cpp ////////////////

#include "maze.h" #include #include #include

using namespace std;

maze::maze():graph() { cin >> start; cin >> exit; }

void maze::dfs(vector &pred) { pred[start] = -2; // start has been visited, but has no predecessor // a vertex u has been visited if and only if pred[u] != -1

if(start == exit) return; stack S; S.push(start); int current, nbr; vnodeptr cursor; while(!S.empty()) { current = S.top(); if(current == exit) { return; } cursor = adjList[current]; while(cursor != nullptr && pred[cursor->v] != -1) { cursor = cursor->next; } if(cursor == nullptr) { // back out S.pop(); // search will continue from the beginning of the while loop } else { nbr = cursor->v; pred[nbr] = current; S.push(nbr); } } }

void maze::print_dfs_exitpath() { vector pred(size,-1); dfs(pred); if(pred[exit] == -1) cout void maze::bfs(vector &pred) { int nbr, current; vnodeptr cursor; pred[start] = -2; // start has been visited, but has no predecessor // a vertex u has been visited if and only if pred[u] != -1 queue Q;

// Complete the code for this function

}

void maze::print_bfs_exitpath() { vector pred(size,-1); bfs(pred); if(pred[exit] == -1) cout

void maze::printPath(int u,vector pred) { if(pred[u] == -2) cout

//////////////// maze.h ////////////////

#include "graph.h"

class maze:public graph { public: maze(); void dfs(vector &pred); void print_dfs_exitpath(); void bfs(vector &pred); void print_bfs_exitpath(); void printPath(int u, vector pred); private: int start; int exit; };

//////////////// main.cpp ////////////////

#include #include "maze.h"

using namespace std;

int main() { maze RatHaus; RatHaus.print_dfs_exitpath(); cout

Example output for DFS.

Input: 6 2 3 5 -1 5 3 2 4 -1 0145 -1 Adjacency list of vertex 2: 5-4->1-0 0 1 5 -1 1 2 5 -1 0 1 2 3 4 -1 2 3 Correct Output: 2->5->4->1->3 Input: 6 2 3 5 -1 5 3 2 4 -1 0145 -1 Adjacency list of vertex 2: 5-4->1-0 0 1 5 -1 1 2 5 -1 0 1 2 3 4 -1 2 3 Correct Output: 2->5->4->1->3