chap graphs the adjacency matrix often requires higher asymptotic cost for an algorithm than would result if the adjacency list were used the reason is that it is common for graph algorithm to visit each neighbor of each vertex using the adjacency listonly the actual edges connecting vertex to its neighbors are examined howeverthe adjacency matrix must look at each of its |vpotential edgesyielding total cost of th(| |time when the algorithm might otherwise require only th(| |+| |time this is considerable disadvantage when the graph is sparsebut not when the graph is closer to full graph implementations we next turn to the problem of implementing graph class figure shows an abstract class defining an adt for graphs vertices are defined by an integer index value in other wordsthere is vertex vertex and so on we can assume that graph application stores any additional information of interest about given vertex elsewheresuch as name or application-dependent value note that this adt is not implemented using genericbecause it is the graph class usersresponsibility to maintain information related to the vertices themselves the graph class has no knowledge of the type or content of the information associated with vertexonly the index number for that vertex abstract class graph has methods to return the number of vertices and edges (methods and erespectivelyfunction weight returns the weight of given edgewith that edge identified by its two incident vertices for examplecalling weight( on the graph of figure (cwould return if no such edge existsthe weight is defined to be so calling weight( on the graph of figure (cwould return functions setedge and deledge set the weight of an edge and remove an edge from the graphrespectively againan edge is identified by its two incident vertices setedge does not permit the user to set the weight to be because this value is used to indicate non-existent edgenor are negative edge weights permitted functions getmark and setmark get and setrespectivelya requested value in the mark array (described belowfor vertex nearly every graph algorithm presented in this will require visits to all neighbors of given vertex two methods are provided to support this they work in manner similar to linked list access functions function first takes as input vertex vand returns the edge to the first neighbor for (we assume the neighbor list is sorted by vertex numberfunction next takes as input vertices and and returns the index for the vertex forming the next edge with after on '