You are required to use ADJACENCY LIST o represent arcs of graph G. Input: Numbe
ID: 3671531 • Letter: Y
Question
You are required to use ADJACENCY LIST o represent arcs of graph G. 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 LIST o 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.
Good Luck
Abdullah N. Arslan
For a graph with 15 vertices, sample input for the graph-creation:
15
1 7
1 2
1 14
2 4
3 1
3 5
3 9
3 8
4 8
4 10
4 1
5 11
5 13
5 15
6 12
7 2
7 6
7 3
8 2
9 11
9 15
10 14
10 6
11 8
12 9
13 12
13 14
14 7
14 12
14 15
You are required to use ADJACENCY LIST o represent arcs of graph G. 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 LIST o 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.
Good Luck
Abdullah N. Arslan
For a graph with 15 vertices, sample input for the graph-creation:
15
1 7
1 2
1 14
2 4
3 1
3 5
3 9
3 8
4 8
4 10
4 1
5 11
5 13
5 15
6 12
7 2
7 6
7 3
8 2
9 11
9 15
10 14
10 6
11 8
12 9
13 12
13 14
14 7
14 12
14 15
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 LIST o 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.
Good Luck
Abdullah N. Arslan
For a graph with 15 vertices, sample input for the graph-creation:
15
1 7
1 2
1 14
2 4
3 1
3 5
3 9
3 8
4 8
4 10
4 1
5 11
5 13
5 15
6 12
7 2
7 6
7 3
8 2
9 11
9 15
10 14
10 6
11 8
12 9
13 12
13 14
14 7
14 12
14 15
Explanation / Answer
#include <iostream>
using namespace std;
int main()
{
int graph[50][50];
int i,j;
int n,k;
int source,destination;
cout << "Enter the Number of vertices" << endl;
cin >> n;
k=0;
while(k<n){
for(i=0;i<n;i++){
for(j=0;j<n;j++){
graph[i][j]=1;
}
}
k++;
}
for(i=0;i<n;i++){
for(j=0;j<n;j++){
cout << graph[i][j];
}
cout << endl;
}
cout << "Directed Graph is READY" << endl;
cout << "Enter the edges source and destination" << endl;
cin >> source >> destination;
if(graph[source][destination]==1){
cout << "REACHABLE" << endl;
}
else{
cout << "NOT REACHABLE" << endl;
}
return 0;
}
Related Questions
Hire Me For All Your Tutoring Needs
Integrity-first tutoring: clear explanations, guidance, and feedback.
Drop an Email at
drjack9650@gmail.com
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.