1 Your Tasks: Basic Part The Setting. In this assignment, we are going to build
ID: 3776995 • Letter: 1
Question
1 Your Tasks: Basic Part
The Setting. In this assignment, we are going to build a class “Graph”. We are using the adjacency matrix method to represent a graph. That is, suppose there are n vertices which we call them v0, v1, . . . , vn1. We use a 2-D matrix pointed by adjmatrix to store the edges. In particular, adjmatrix[i][j] stores the weight of the edge vi vj . In this assignment, we consider directed graphs, and if adjmatrix[i][j] is 0, this means the edge vi vj does not exist. For simplicity, we assume that all the edges, if existing, have positive weights.
Task 1. You are going to build two constructors, the default constructor and another one that takes inputs a graph with n nodes and an adjacency matrix pointed by m. For the default constructor, you can initialize the graph in any way you like. For the second constructor, you need to copy the input graph to the current object. Make sure you new a correct 2-D matrix for the current object, and then copy the input graph to the current object’s adjacency matrix.
Task 2. Write the following three functions. (1) The adj function takes input two indices i and j. Return true if nodes i and j have a direct edge. (2) The outdegree function takes input a node index, and returns an integer that represents how many out-edges are connected to the input node. (3) The indegree function is similar to the outdegree function.
Task 3. Write some test cases for your code.
2 Your Tasks: Advance Part
Task 4. You are going to implement the two traversal methods, namely the BFS and DFS. For each method, you need to print (i.e., cout) the vertices when the algorithm traverses a node. It would be helpful if you write some helper functions/data structures, but you should make your choices.
Task 5. Write a function that determines whether the graph is strongly connected or not. A graph is strongly connected if and only if every node can reach any other nodes. You can use the ideas in Task 4 to help you.
Task 6. Write a function that determines whether the graph contains a cycle. You should notice that the graphs we consider here are directed graphs. The idea of DFS can be helpful in this task.
Task 7. Write some test cases for your code
Explanation / Answer
Solution:
#include <iostream>
#include <cstdlib>
using namespace std;
#define MAX 20
class GraphAM
{
private:
int n;
int **adj;
bool *visited;
public:
GraphAM(int n)
{
this->n = n;
visited = new bool [n];
adj = new int* [n];
for (int i = 0; i < n; i++)
{
adj[i] = new int [n];
for(int j = 0; j < n; j++)
{
adj[i][j] = 0;
}
}
}
void add_edge(int o, int d)
{
if( o > n || d > n || o < 0 || d < 0)
{
cout<<"Invalid edge! ";
}
else
{
adj[o - 1][d - 1] = 1;
}
}
void display()
{
int i,j;
for(i = 0;i < n;i++)
{
for(j = 0; j < n; j++)
cout<<adj[i][j]<<" ";
cout<<endl;
}
}
};
int main()
{
int nodes, max_edges, o, d;
cout<<"Enter number of nodes: ";
cin>>nodes;
GraphAM adjmatrix(nodes);
max_edges = nodes * (nodes - 1);
for (int i = 0; i < max_edges; i++)
{
cout<<"Enter edge (-1 -1 to exit): ";
cin>>o>>d;
if((o == -1) && (d == -1))
break;
adjmatrix.add_edge(o, d);
}
cout<<"Adjacent matrix is: ";
adjmatrix.display();
return 0;
}
Sample Output:
Enter number of nodes: 5
Enter edge (-1 -1 to exit): 1 2
Enter edge (-1 -1 to exit): 3 4
Enter edge (-1 -1 to exit): 1 4
Enter edge (-1 -1 to exit): 2 5
Enter edge (-1 -1 to exit): 2 5
Enter edge (-1 -1 to exit): 2 1
Enter edge (-1 -1 to exit): 1 5
Enter edge (-1 -1 to exit): 1 8
Invalid edge!
Enter edge (-1 -1 to exit): 1 4
Enter edge (-1 -1 to exit): -1 -1
Adjacent matrix is:
0 1 0 1 1
1 0 0 0 1
0 0 0 1 0
0 0 0 0 0
0 0 0 0 0
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.