data structures for graphs in this sectionwe introduce four data structures for representing graph in each representationwe maintain collection to store the vertices of graph howeverthe four representations differ greatly in the way they organize the edges in an edge listwe maintain an unordered list of all edges this minimally sufficesbut there is no efficient way to locate particular edge (uv)or the set of all edges incident to vertex in an adjacency listwe maintainfor each vertexa separate list containing those edges that are incident to the vertex the complete set of edges can be determined by taking the union of the smaller setswhile the organization allows us to more efficiently find all edges incident to given vertex an adjacency map is very similar to an adjacency listbut the secondary container of all edges incident to vertex is organized as maprather than as listwith the adjacent vertex serving as key this allows for access to specific edge (uvin ( expected time an adjacency matrix provides worst-case ( access to specific edge (uvby maintaining an matrixfor graph with vertices each entry is dedicated to storing reference to the edge (uvfor particular pair of vertices and vif no such edge existsthe entry will be none summary of the performance of these structures is given in table we give further explanation of the structures in the remainder of this section operation vertex countedge countverticesedgesget edge( ,vdegree(vincident edges(vinsert vertex(xremove vertex(vinsert edge( , ,xremove edge(eedge list ( ( (no(mo(mo(mo(mo( (mo( ( adj list ( ( (no(mo(min(du dv ) ( (dv ( (dv ( ( adj map ( ( (no(mo( exp ( (dv ( (dv ( exp ( exp adj matrix ( ( (no(mo( (no(no( ( ( ( table summary of the running times for the methods of the graph adtusing the graph representations discussed in this section we let denote the number of verticesm the number of edgesand dv the degree of vertex note that the adjacency matrix uses ( spacewhile all other structures use ( mspace