Editing Adjacency matrix (section)

==Data structures==
The adjacency matrix may be used as a [[data structure]] for the [[Graph (abstract data type)|representation of graphs]] in computer programs for manipulating graphs. The main alternative data structure, also in use for this application, is the [[adjacency list]].<ref>{{harvtxt|Goodrich|Tamassia|2015}}, p.&nbsp;361: "There are two data structures that people often use to represent graphs, the adjacency list and the adjacency matrix."</ref><ref name="clrs">{{citation |author-link=Thomas H. Cormen |first1=Thomas H. |last1=Cormen |author-link2=Charles E. Leiserson |first2=Charles E. |last2=Leiserson |author-link3=Ronald L. Rivest |first3=Ronald L. |last3=Rivest |author-link4=Clifford Stein |first4=Clifford |last4=Stein |year=2001 |title=[[Introduction to Algorithms]] |edition=Second |publisher=MIT Press and McGraw-Hill |isbn=0-262-03293-7 |chapter=Section 22.1: Representations of graphs |pages=527–531 }}.</ref>

The space needed to represent an adjacency matrix and the time needed to perform operations on them is dependent on the [[matrix representation]] chosen for the underlying matrix. [[Sparse matrix representation]]s only store non-zero matrix entries and implicitly represent the zero entries. They can, for example, be used to represent [[sparse graph]]s without incurring the space overhead from storing the many zero entries in the adjacency matrix of the sparse graph. In the following section the adjacency matrix is assumed to be represented by an [[array data structure]] so that zero and non-zero entries are all directly represented in storage.

Because each entry in the adjacency matrix requires only one bit, it can be represented in a very compact way, occupying only {{math|{{pipe}}''V''{{thinsp}}{{pipe}}<sup>2</sup>{{hairsp}}/{{hairsp}}8}} bytes to represent a directed graph, or (by using a packed triangular format and only storing the lower triangular part of the matrix) approximately {{math|{{pipe}}''V''{{thinsp}}{{pipe}}<sup>2</sup>{{hairsp}}/{{hairsp}}16}} bytes to represent an undirected graph. Although slightly more succinct representations are possible, this method gets close to the information-theoretic lower bound for the minimum number of bits needed to represent all {{mvar|n}}-vertex graphs.<ref>{{citation
 | last = Turán | first = György
 | doi = 10.1016/0166-218X(84)90126-4
 | issue = 3
 | journal = [[Discrete Applied Mathematics]]
 | mr = 749658
 | pages = 289–294
 | title = On the succinct representation of graphs
 | volume = 8
 | year = 1984
| doi-access = 
 }}.</ref> For storing graphs in [[text file]]s, fewer bits per byte can be used to ensure that all bytes are text characters, for instance by using a [[Base64]] representation.<ref>{{citation|first1=Brendan|last1=McKay|author-link=Brendan McKay (mathematician)|title=Description of graph6 and sparse6 encodings|url=http://cs.anu.edu.au/~bdm/data/formats.txt|access-date=2012-02-10|archive-date=2001-04-30|archive-url=https://web.archive.org/web/20010430081526/http://cs.anu.edu.au/~bdm/data/formats.txt|url-status=live}}.</ref> Besides avoiding wasted space, this compactness encourages [[locality of reference]].
However, for a large [[sparse graph]], adjacency lists require less storage space, because they do not waste any space representing edges that are ''not'' present.<ref name="clrs"/><ref name="gt"/>

An alternative form of adjacency matrix (which, however, requires a larger amount of space) replaces the numbers in each element of the matrix with pointers to edge objects (when edges are present) or null pointers (when there is no edge).<ref name="gt"/> It is also possible to store [[weighted graph|edge weights]] directly in the elements of an adjacency matrix.<ref name="clrs"/>

Besides the space tradeoff, the different data structures also facilitate different operations. Finding all vertices adjacent to a given vertex in an adjacency list is as simple as reading the list, and takes time proportional to the number of neighbors. With an adjacency matrix, an entire row must instead be scanned, which takes a larger amount of time, proportional to the number of vertices in the whole graph. On the other hand, testing whether there is an edge between two given vertices can be determined at once with an adjacency matrix, while requiring time proportional to the minimum degree of the two vertices with the adjacency list.<ref name="clrs"/><ref name="gt">{{citation|title=Algorithm Design and Applications|first1=Michael T.|last1=Goodrich|author1-link=Michael T. Goodrich|first2=Roberto|last2=Tamassia|author2-link=Roberto Tamassia|publisher=Wiley|year=2015|page=363}}.</ref>