Only allow to fill in the missing code for the function vector maze::bfs():

Test Input and Correct Output

Note: the order of the vertices in the adjacency lists will be the reverse of the order in which they appear in the input file because they are inserted at the front of the list.

Input:

6

2

3

2 3 5 -1

2 3 4 5 -1

0 1 4 5 -1

0 1 5 -1

1 2 5 -1

0 1 2 3 4 -1

Correct Output

2 5 3

#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; }