Editing Graph theory (section)

=== Tabular: Graph data structures ===
{{main|Graph (abstract data type)}}
The tabular representation lends itself well to computational applications. There are different ways to store graphs in a computer system. The [[data structure]] used depends on both the graph structure and the [[algorithm]] used for manipulating the graph. Theoretically one can distinguish between list and matrix structures but in concrete applications the best structure is often a combination of both. List structures are often preferred for [[sparse graph]]s as they have smaller memory requirements. [[Matrix (mathematics)|Matrix]] structures on the other hand provide faster access for some applications but can consume huge amounts of memory. Implementations of sparse matrix structures that are efficient on modern parallel computer architectures are an object of current investigation.<ref>{{Cite book | last1 = Kepner | first1 = Jeremy| last2 = Gilbert | first2 = John| title = Graph Algorithms in the Language of Linear Algebra| date = 2011| pages = 1171458|isbn=978-0-898719-90-1| publisher = SIAM | url = https://my.siam.org/Store/Product/viewproduct/?ProductId=106663}}</ref>

List structures include the [[edge list]], an array of pairs of vertices, and the [[adjacency list]], which separately lists the neighbors of each vertex: Much like the edge list, each vertex has a list of which vertices it is adjacent to.

Matrix structures include the [[incidence matrix]], a matrix of 0's and 1's whose rows represent vertices and whose columns represent edges, and the [[adjacency matrix]], in which both the rows and columns are indexed by vertices. In both cases a 1 indicates two adjacent objects and a 0 indicates two non-adjacent objects. The [[degree matrix]] indicates the degree of vertices. The [[Laplacian matrix]] is a modified form of the adjacency matrix that incorporates information about the [[degree (graph theory)|degrees]] of the vertices, and is useful in some calculations such as [[Kirchhoff's theorem]] on the number of [[spanning tree]]s of a graph.
The [[distance matrix]], like the adjacency matrix, has both its rows and columns indexed by vertices, but rather than containing a 0 or a 1 in each cell it contains the length of a [[shortest path]] between two vertices.