write C++ code Input: Number n of vertices (i.e. vertex set is {1,2, …,n}), and
ID: 3669595 • Letter: W
Question
write C++ code
Input: Number n of vertices (i.e. vertex set is {1,2, …,n}), and a list of edges (i,j) for 1 i,j n for a directed graph G. After this part, read a list of pair of vertices, one pair at a time.
Output: For each given pair of vertices i, j, output “reachable” if vertex j is reachable from vertex i via a directed path in G; “not reachable”, otherwise. Note that a directed path length can be larger than one.
Goal: Create the directed graph G from the given input, and decide for every given pair of vertices if the second vertex is reachable from the first vertex via a directed path in G. Assume that every vertex is reachable from itself in zero steps.
Hint: You can maintain an array of vertices in which you mark reachable vertices.
Example input file:
5
1 2
2 5
3 4
1 3
Example dialog (still during the same execution of the program):
Graph G is constructed
1 2 <ENTER>
reachable
1 5 <ENTER>
reachable
1 4 <ENTER>
not reachable
2 4 <ENTER>
not reachable
5 5 0 <ENTER>
reachable
In this assignment, you write a C++ program for Problem A. Both correctness and efficiency of your programs are important. You are required to use ADJACENCY MATRIX to represent arcs of graph G. See a large input file for creating G on Page 5 (the last page). Test it with your list of pairs of vertices for reachable/not reachable queries.
Explanation / Answer
#include<iostream>
#include <list>
using namespace std;
// This class represents a directed graph using adjacency list
// representation
class Graph
{
int V; // No. of vertices
list<int> *adj; // Pointer to an array containing adjacency lists
public:
Graph(int V); // Constructor
void addEdge(int v, int w); // function to add an edge to graph
bool isReachable(int s, int d);
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
// A BFS based function to check whether d is reachable from s.
bool Graph::isReachable(int s, int d)
{
// Base case
if (s == d)
return true;
// Mark all the vertices as not visited
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
// Create a queue for BFS
list<int> queue;
// Mark the current node as visited and enqueue it
visited[s] = true;
queue.push_back(s);
// it will be used to get all adjacent vertices of a vertex
list<int>::iterator i;
while (!queue.empty())
{
// Dequeue a vertex from queue and print it
s = queue.front();
queue.pop_front();
// Get all adjacent vertices of the dequeued vertex s
// If a adjacent has not been visited, then mark it visited
// and enqueue it
for (i = adj[s].begin(); i != adj[s].end(); ++i)
{
// If this adjacent node is the destination node, then
// return true
if (*i == d)
return true;
// Else, continue to do BFS
if (!visited[*i])
{
visited[*i] = true;
queue.push_back(*i);
}
}
}
// If BFS is complete without visiting d
return false;
}
// Driver program to test methods of graph class
int main()
{
// Create a graph given in the above diagram
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
int u = 1, v = 3;
if(g.isReachable(u, v))
cout<< " There is a path from " << u << " to " << v;
else
cout<< " There is no path from " << u << " to " << v;
u = 3, v = 1;
if(g.isReachable(u, v))
cout<< " There is a path from " << u << " to " << v;
else
cout<< " There is no path from " << u << " to " << v;
return 0;
}
#include<iostream>
#include <list>
using namespace std;
// This class represents a directed graph using adjacency list
// representation
class Graph
{
int V; // No. of vertices
list<int> *adj; // Pointer to an array containing adjacency lists
public:
Graph(int V); // Constructor
void addEdge(int v, int w); // function to add an edge to graph
bool isReachable(int s, int d);
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
// A BFS based function to check whether d is reachable from s.
bool Graph::isReachable(int s, int d)
{
// Base case
if (s == d)
return true;
// Mark all the vertices as not visited
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
// Create a queue for BFS
list<int> queue;
// Mark the current node as visited and enqueue it
visited[s] = true;
queue.push_back(s);
// it will be used to get all adjacent vertices of a vertex
list<int>::iterator i;
while (!queue.empty())
{
// Dequeue a vertex from queue and print it
s = queue.front();
queue.pop_front();
// Get all adjacent vertices of the dequeued vertex s
// If a adjacent has not been visited, then mark it visited
// and enqueue it
for (i = adj[s].begin(); i != adj[s].end(); ++i)
{
// If this adjacent node is the destination node, then
// return true
if (*i == d)
return true;
// Else, continue to do BFS
if (!visited[*i])
{
visited[*i] = true;
queue.push_back(*i);
}
}
}
// If BFS is complete without visiting d
return false;
}
// Driver program to test methods of graph class
int main()
{
// Create a graph given in the above diagram
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
int u = 1, v = 3;
if(g.isReachable(u, v))
cout<< " There is a path from " << u << " to " << v;
else
cout<< " There is no path from " << u << " to " << v;
u = 3, v = 1;
if(g.isReachable(u, v))
cout<< " There is a path from " << u << " to " << v;
else
cout<< " There is no path from " << u << " to " << v;
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.