Question

Write a C++ or Java program name that conducts the BFS traversal of a graph and displays city names in the range of hop(s) from a starting city

Input format: This is a sample input from a user.

4 Monterey LA SF SD 6 Monterey LA LA SD SD Monterey SF Monterey SF LA SF SD Monterey 2

The first line (= 4 in the example) indicates that there are four vertices in the graph. The following four lines describe the names of four cities. The next line (= 6 in the example) indicates the number of edges in the graph. The following six lines are the edge information with the “source city” and “destination city”. The following city (= Monterey in the example) is the starting city, and the last line (= 2 in the example) indicates the hops from the starting city. Thus, the problem is to list the city names that can be reached from the source in two hops. This is the graph with the input information.

Sample Run 0: Assume that the user typed the following lines

4

Monterey

LA

SF

SD

6

Monterey LA

LA SD

SD Monterey

SF Monterey

SF LA

SF SD

Monterey

2

This is the correct output. Your program should present the city names with the hop in the ascending order like below.  Note that LA can be reached from Monterey in one hop, Monterey in zero hop, and SD in two hops. For the problem, you can assume that the city name is always one word. Also, your program should consider only the minimum number of hops from the starting city.

LA:1

Monterey:0

SD:2

Sample Run 1: Assume that the user typed the following lines

4

Monterey

LA

SF

SD

6

Monterey LA

LA SD

SD Monterey

SF Monterey

SF LA

SF SD

LA

1

This is the correct output.

LA:0

SD:1

Sample Run 2: Assume that the user typed the following lines

5

Fresno

LA

SD

SF

NYC

6

SD LA

SD NYC

LA NYC

SF Fresno

SF SD

Fresno SD

SF

2

This is the correct output.

Fresno:1

LA:2

NYC:2

SD:1

SF:0

Answer 1

C++ code

#include <bits/stdc++.h>
using namespace std;

unordered_map<string, int> m1; //map to store integer corresponding to each city for ease of calculation
unordered_map<int, string> m2; // reverse mapping for m1(city corresponding to integer)
void bfs(int start, int n, vector<int> *adj, int hops)
{
queue<int> q; //bfs queue
bool visited[n] = {0};
q.push(start);
q.push(-1); // -1 is used as the delimiter to track the starting of new level
visited[start] = 1;
vector<pair<string, int>> ans; // ans vector for storing the cities reached
int level = 0;
while(!q.empty())
{
int top = q.front();
q.pop();
if(top == -1)
{
level++;
if(!q.empty() && level <= hops)
q.push(-1);
else
break;
}
else
{
ans.push_back(make_pair(m2[top], level));
for(int x: adj[top])
{
if(!visited[x])
{
q.push(x);
visited[x] = 1;
}
}
}
}

sort(ans.begin(), ans.end()); //sorting the ans vector according to city names
for(auto x: ans)
{
cout<<x.first<<" "<<x.second<<endl;
}
}

int main()
{
m1.clear();
m2.clear();
int vertices, edges;
cin>>vertices;
for(int i=0;i<vertices;i++)
{
string city;
cin>>city;
m1[city] = i; //mapping city to int
m2[i] = city; //reverse mapping
}

cin>>edges;
vector<int> *adj = new vector<int>[vertices]; //adjacency list for storing graph
for(int i=0;i<edges;i++)
{
string city1, city2;
cin>>city1;
cin>>city2;
int u = m1[city1];
int v = m1[city2];
adj[u].push_back(v);
}

string startcity;
cin>>startcity;
int start, hops;
start = m1[startcity];
cin>>hops;

bfs(start, vertices, adj, hops);
}