Use C++ language: Problem A: Input: Number n of vertices (i.e. vertex set is {1,

Question

Use C++ language:

Problem A:

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

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.

Explanation / Answer

This is a C++ Program to check and find if the path between two nodes exists. By running DFS on given graph we can find out whether path exists between two nodes.

Here is source code of the C++ Program to Find Path Between Two Nodes in a Graph. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

Output:

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

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