1 searching and traversing digraphs a do problem 21 from page 910 of the textbook yo 5346816

1. [Searching and Traversing Digraphs]

a)Do problem 21 from page 910 of the textbook

You must define a Matrix Abstract Data Type.

You must use templates to make it as generic as possible.

Use a two-dimensional, dynamically allocated array to implementyour Matrix ADT.

You must declare and implement:

o one or more constructors,

o a destructor,

o the operators +, *, =,

o a showStructure (or print ) function to show your matrices

o a function to create the identity matrix

o a function to set the adjacency matrix

o a function Reach to compute the reachability matrix R

o etc.

Here is what problem 21 states:

If A is an n x n adjacency matrix for a directed graph, then theentry in the ith row andjth column of A^k is equal to the number ofpaths of length k from the ith vertex to the jth vertex in thisgraph. The reachability matrix for a directed diagraph.Thereachability matrix R of a diagraph is the n x n matrix definedby

R = I + A + A^2 + … + A^(n-1)

Where I is the n x n identity matrix having ones on the diagonal (from upper left corner to lower right corner) and zeros off. In thediagraph, there is a path from vertex i to vertex j if and only ifthe entry in row i and column j of R is nonzero. Write a functionto find the reachablility matrix for a directed graph.