Fill in only the missing code for the function vector maze::bfs() for the program given below Do not add any other lines of code that wasn't already defined within this program or modify/add any lines of code to any functions besides the vector maze::bfs() function.

#include #include #include #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 maze { public: maze(); // interactive constructor using cin void print_dfs_exitpath(); void print_bfs_exitpath(); private: int size; int start; int exit; vector adjList; stack dfs(); vector bfs(); };

void printBottomToTop(stack S); void printPredecessorPath(vector pred);

void printBottomToTop(stack S) { stack tmp; while(!S.empty()) { tmp.push(S.top()); S.pop(); } while(!tmp.empty()) { cout << tmp.top(); tmp.pop(); if(!tmp.empty()) cout << "->"; else cout << endl; } }

void printPredecessorPath(vector pred,int target) { stack S; int current = target; while(pred[current] >= 0) { S.push(current); current = pred[current]; } while(S.size() > 1) { cout << S.top() << "->"; S.pop(); } cout << S.top() << endl; }

maze::maze() { int vertex; cin >> size; cin >> start; cin >> exit; assert(0 <= start && start < size); assert(0 <= exit && exit < size);

adjList.resize(size,NULL); for(int i = 0; i < size; ++i) { cin >> vertex; while(vertex != -1) { if(vertex == i) { cerr << "Invalid adjacency; terminating" << endl; assert(vertex != i); } adjList[i] = new vnode(vertex,adjList[i]); // insert at begining cin >> vertex; } } }

stack maze::dfs() { int current, nbr; vector visited(size,false); stack path; visited[start] = true; path.push(start); while(!path.empty()) { current = path.top(); if(current == exit) { break; } vnodeptr cursor = adjList[current]; while(cursor != nullptr && visited[cursor->v]) cursor = cursor->next; if(cursor != nullptr) { // found an open neighbor nbr = cursor->v; visited[nbr] = true; path.push(nbr); } else { // back out path.pop(); if(path.empty()) { // backed out from start break; } } // Continue search from the newly discovered vertex } return path; }

void maze::print_dfs_exitpath() { stack path = dfs(); /if(path.empty()) cout << "No way out" << endl; printBottomToTop(path); }

void maze::print_bfs_exitpath() { vector pred = bfs(); if (pred[exit] == -1) cout << "No way out" << endl; else printPredecessorPath(pred,exit); }

vector maze::bfs() // breadth-first search { int current = start, nbr; queue Q; vector pred(size,-1); pred[start] = -2; Q.push(start); while(!Q.empty()) { current = Q.front(); Q.pop();

// Fill in the missing code

} return pred; }

int main() { maze RatHaus; RatHaus.print_bfs_exitpath(); cout << endl; return 0; }