find path between two vertices in directed graph the nodes should be reachable w

Question

find path between two vertices in directed graph

the nodes should be reachable with mediate nodes also as (1 2)(2 5) like 1->2->5 like wise

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 ivia a directed path in G; “not reachable”, otherwise. Note that a directed path lengthcan 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

need to consider another array

Example dialog (still during the same execution of the program):

Graph G is constructed

1 2

reachable

1 5 1->2->5

reachable

1 4

not reachable

2 4

not reachable

5 5 0

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

// ++ program to check if there is exist a path between two vertices of a graph. #include #include using namespace std; // This class represents a directed graph using adjacency list representation class Graph { int V; // No. of vertices list *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[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

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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