adjacency matrix structure the adjacency matrix structure for graph augments the edge list structure with matrix (that isa two-dimensional arrayas in section )which allows us to locate an edge between given pair of vertices in worst-case constant time in the adjacency matrix representationwe think of the vertices as being the integers in the set { and the edges as being pairs of such integers this allows us to store references to edges in the cells of two-dimensional array specificallythe cell [ijholds reference to the edge (uv)if it existswhere is the vertex with index and is the vertex with index if there is no such edgethen [ijnone we note that array is symmetric if graph is undirectedas [ijajifor all pairs and (see figure the most significant advantage of an adjacency matrix is that any edge (uvcan be accessed in worst-case ( timerecall that the adjacency map supports that operation in ( expected time howeverseveral operation are less efficient with an adjacency matrix for exampleto find the edges incident to vertex vwe must presumably examine all entries in the row associated with vrecall that an adjacency list or map can locate those edges in optimal (deg( )time adding or removing vertices from graph is problematicas the matrix must be resized furthermorethe ( space usage of an adjacency matrix is typically far worse than the ( mspace required of the other representations althoughin the worst casethe number of edges in dense graph will be proportional to most real-world graphs are sparse in such casesuse of an adjacency matrix is inefficient howeverif graph is densethe constants of proportionality of an adjacency matrix can be smaller than that of an adjacency list or map in factif edges do not have auxiliary dataa boolean adjacency matrix can use one bit per edge slotsuch that [ijtrue if and only if associated (uvis an edge (ah (bfigure (aan undirected graph (ba schematic representation of the auxiliary adjacency matrix structure for gin which vertices are mapped to indices to although not diagrammed as suchwe presume that there is unique edge instance for each edgeand that it maintains references to its endpoint vertices we also assume that there is secondary edge list (not pictured)to allow the edgesmethod to run in (mtimefor graph with edges