one simple way to represent graph is to use two-dimensional array this is known as an adjacency matrix representation for each edge (uv)we set [ ][vto trueotherwise the entry in the array is false if the edge has weight associated with itthen we can set [ ][vequal to the weight and use either very large or very small weight as sentinel to indicate nonexistent edges for instanceif we were looking for the cheapest airplane routewe could represent nonexistent flights with cost of if we were lookingfor some strange reasonfor the most expensive airplane routewe could use (or perhaps to represent nonexistent edges although this has the merit of extreme simplicitythe space requirement is (| | )which can be prohibitive if the graph does not have very many edges an adjacency matrix is an appropriate representation if the graph is dense| (| | in most of the applications that we shall seethis is not true for instancesuppose the graph represents street map assume manhattan-like orientationwhere almost all the streets run either north-south or east-west thereforeany intersection is attached to roughly four streetsso if the graph is directed and all streets are two-waythen | |vif there are , intersectionsthen we have , -vertex graph with , edge entrieswhich would require an array of size , , most of these entries would contain zero this is intuitively badbecause we want our data structures to represent the data that are actually there and not the data that are not present if the graph is not densein other wordsif the graph is sparsea better solution is an adjacency list representation for each vertexwe keep list of all adjacent vertices the space requirement is then (| | |)which is linear in the size of the graph the abstract representation should be clear from figure if the edges have weightsthen this additional information is also stored in the adjacency lists adjacency lists are the standard way to represent graphs undirected graphs can be similarly representedeach edge (uvappears in two listsso the space usage essentially doubles common requirement in graph algorithms is to find all vertices adjacent to some given vertex vand this can be donein time proportional to the number of such vertices foundby simple scan down the appropriate adjacency list there are several alternatives for maintaining the adjacency lists firstobserve that the lists themselves can be maintained in either vectors or lists howeverfor sparse graphswhen using vectorsthe programmer may need to initialize each vector with smaller capacity than the defaultotherwisethere could be significant wasted space because it is important to be able to quickly obtain the list of adjacent vertices for any vertexthe two basic options are to use map in which the keys are vertices and the values are adjacency listsor to maintain each adjacency list as data member of vertex class the first option is arguably simplerbut the second option can be fasterbecause it avoids repeated lookups in the map in the second scenarioif the vertex is string (for instancean airport nameor the name of street intersection)then map can be used in which the key is the vertex name and the value is vertex (typically pointer to vertex)and each vertex object keeps list of (pointers to theadjacent vertices and perhaps also the original string name when we speak of linear-time graph algorithmso(| | |is the running time we require