USA: +1 (725) 712-1730 
Sign in
C++
In this program, you create a map and find the route from a source location to a destination location. You will use structure(s), pointer(s) and class(es) to accomplish this task. The letters of the alphabet represent the locations. Each line represents a highway and each location has one exit highway and one entry highway. You may only leave a location through its exit highway and enter it through its entry highway. (For example The route from location A to D using this map is A rightarrow E rightarrow C rightarrow B rightarrow D) Your code will implement this. First, you will begin by creating the map above in your code using class(es), structure(s), pointer(s) and anything else you may want to use. Once you have the map, you will prompt the user to enter new names for the locations represented by A, B, C, D, E, above. Once you have accomplished that, you have created your map. Next, you will prompt the user for the starting location and destination location. You will use the map to figure out and then display the route from the starting location to the destination location. You must keep track of how many times a location is chosen as a destination. You must, then, display the following menu and continue to do so until the user decides to exit the program: C-to enter another source & destination pair P – to see the most popular destination locations E-to exit If the user enters P, you must display the locations from most popular (chosen the most number of times as destination) to least popular. If two or more locations have been chosen as the destination the same number of times, list them in alphabetical order. Please remember to place appropriate error checks
Expert Answer
ANSWER::
#include<iostream>
#include <list>
using namespace std;
class Graph
{
int V;
list<int> *adj;
void printAllPathsUtil(int , int , bool [], int [], int &);
public:
Graph(int V);
void addEdge(int u, int v);
void printAllPaths(int s, int d);
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int u, int v)
{
adj[u].push_back(v);
}
void Graph::printAllPaths(int s, int d)
{
bool *visited = new bool[V];
int *path = new int[V];
int path_index = 0;
for (int i = 0; i < V; i++)
visited[i] = false;
printAllPathsUtil(s, d, visited, path, path_index);
}
void Graph::printAllPathsUtil(int u, int d, bool visited[],
int path[], int &path_index)
{
visited[u] = true;
path[path_index] = u;
path_index++;
if (u == d)
{
for (int i = 0; i<path_index; i++)
cout << path[i] << ” “;
cout << endl;
}
else
{
list<int>::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i)
if (!visited[*i])
printAllPathsUtil(*i, d, visited, path, path_index);
}
path_index–;
visited[u] = false;
}
int main()
{
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(0, 3);
g.addEdge(2, 0);
g.addEdge(2, 1);
g.addEdge(1, 3);
int s = 2, d = 3;
cout << “Following are all different paths from ” << s
<< ” to ” << d << endl;
g.printAllPaths(s, d);
return 0;
}
