Fill in only the missing code for the function vector<int> maze::bfs() for the p

Question

Fill in only the missing code for the function vector<int> 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<int> maze::bfs() function.

#include<stack>
#include<queue>
#include<vector>
#include <iostream>
#include <cassert>
#include<stack>

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<vnodeptr> adjList;
   stack<int> dfs();
   vector<int> bfs();
};

void printBottomToTop(stack<int> S);
void printPredecessorPath(vector<int> pred);

void printBottomToTop(stack<int> S)
{
stack<int> 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<int> pred,int target)
{
stack<int> 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<int> maze::dfs()
{
int current, nbr;
vector<bool> visited(size,false);
stack<int> 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<int> path = dfs();
     /if(path.empty())
       cout << "No way out" << endl;
     printBottomToTop(path);
}

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

vector<int> maze::bfs() // breadth-first search
{
    int current = start, nbr;
    queue<int> Q;
    vector<int> 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;
}

Explanation / Answer

I feel that the following code will do the required.

What it does is that when we push a node in the queue, at that time we set the predecessor as the current node as that node is visited through current node. The rest is just simple bfs.

vector<int> maze::bfs() // breadth-first search

{

int current = start, nbr;

queue<int> Q;

vector<int> pred(size,-1);

pred[start] = -2;

Q.push(start);

vector<bool> visited(size,false); // This is also required

while(!Q.empty()) {

current = Q.front();

vnodeptr ptr = adjList[current]; // Getting the adj list for current

while(ptr != nullptr) // End of that list

{

if(!visited[ptr->v]) // As bfs only travels on unvisited nodes

{

pred[ptr->v] = current; // Visiting through current node

Q.push(ptr->v); // Pushing in queue

visited[ptr->v] = true;

}

ptr = ptr->next;

}

Q.pop();

}

return pred;

}

Please rate positive if satisfied :D :)

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.