Fill in the missing code for the function vector<int> maze::bfs() in the maze.cp
ID: 3912491 • Letter: F
Question
Fill in the missing code for the function vector<int> maze::bfs() in the maze.cpp file
The appropriate mathematical model for a general maze: an undirected graph with a start node and an exit node
The goal is to find a path from the start to the exit
We can use either of the graph traversal algorithms covered previously
depth-first search; and
breadth-first search
The only difference is that we discontinue the search if we discover the exit vertex
In our model, we will just return the predecessor array, which can the be used to print the exit path
Rather than using a separate Graph class, we build in the adjacency lists as part of the MazeGraph class
The size attribute of the class holds the number of vertices
The vertices are then the integers 0, 1, …, size-1
We define a node type – vnode – that holds a vertex and a next pointer
We will use a vector<vnode *> to hold the adjacency lists
Thus, adjList[i] will be a pointer to the first node of the adjacency list for vertex i
// ------------------------------maze.h----------------------------
#include<stack>
#include<queue>
#include<vector>
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);
// ------------------------------maze.cpp----------------------------
#include "maze.h"
#include <cassert>
#include <iostream>
using namespace std;
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() // depth-first search
{
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;
}
// ------------------------------ test_mazedfs.cpp----------------------------
// Used to test print_dfs_exitpath()
#include <iostream>
#include "maze.h"
using namespace std;
int main()
{
maze RatHaus;
RatHaus.print_dfs_exitpath();
cout << endl;
return 0;
}
// ------------------------------RescueRemy.cpp-----------------------------
// This program should always be run with input redirected to a file
// Use this to test your print_bfs_exitpath method
#include <iostream>
#include "maze.h"
using namespace std;
int main()
{
maze RatHaus; // interactive constructor
RatHaus.print_bfs_exitpath();
cout << endl;
return 0;
}
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
Explanation / Answer
#include "maze.h"
#include <cassert>
#include <iostream>
using namespace std;
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() // depth-first search
{
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
{
bool *visited = new bool[size];
for (int i = 0; i < size; i++)
visited[i] = false;
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
vnodeptr i;
for (auto itr = adjList.begin(); itr < adjList.end(); ++itr)
{
vnodeptr node = *itr;
if (!visited[node->v])
{
visited[node->v] = true;
Q.push(node->v);
}
}
}
return pred;
}
Please find above function with missing code. Let me know for any queries.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.