adjacency map structure in the adjacency list structurewe assume that the secondary incidence collections are implemented as unordered linked lists such collection (vuses space proportional to (deg( ))allows an edge to be added or removed in ( timeand allows an iteration of all edges incident to vertex in (deg( )time howeverthe best implementation of get edge( ,vrequires (min(deg( )deg( ))timebecause we must search through either (uor (vwe can improve the performance by using hash-based map to implement (vfor each vertex specificallywe let the opposite endpoint of each incident edge serve as key in the mapwith the edge structure serving as the value we call such graph representation an adjacency map (see figure the space usage for an adjacency map remains ( )because (vuses (deg( )space for each vertex vas with the adjacency list the advantage of the adjacency maprelative to an adjacency listis that the get edge( ,vmethod can be implemented in expected ( time by searching for vertex as key in ( )or vice versa this provides likely improvement over the adjacency listwhile retaining the worst-case bound of (min(deg( )deg( ))in comparing the performance of adjacency map to other representations (see table )we find that it essentially achieves optimal running times for all methodsmaking it an excellent all-purpose choice as graph representation ( (bfigure (aan undirected graph (ba schematic representation of the adjacency map structure for each vertex maintains secondary map in which neighboring vertices serve as keyswith the connecting edges as associated values although not diagrammed as suchwe presume that there is unique edge instance for each edge of the graphand that it maintains references to its endpoint vertices