Representations
Different data structures for the representation of graphs are used in practice:
- Adjacency list
- Vertices are stored as records or objects, and every vertex stores a list of adjacent vertices. This data structure allows the storage of additional data on the vertices.
- Incidence list
- Vertices and edges are stored as records or objects. Each vertex stores its incident edges, and each edge stores its incident vertices. This data structure allows the storage of additional data on vertices and edges.
- Adjacency matrix
- A two-dimensional matrix, in which the rows represent source vertices and columns represent destination vertices. Data on edges and vertices must be stored externally. Only the cost for one edge can be stored between each pair of vertices.
- Incidence matrix
- A two-dimensional Boolean matrix, in which the rows represent the vertices and columns represent the edges. The entries indicate whether the vertex at a row is incident to the edge at a column.
The following table gives the time complexity cost of performing various operations on graphs, for each of these representations. In the matrix representations, the entries encode the cost of following an edge. The cost of edges that are not present are assumed to be .
| Adjacency list | Incidence list | Adjacency matrix | Incidence matrix | |
|---|---|---|---|---|
| Storage | ||||
| Add vertex | ||||
| Add edge | ||||
| Remove vertex | ||||
| Remove edge | ||||
| Query: are vertices u, v adjacent? (Assuming that the storage positions for u, v are known) | ||||
| Remarks | When removing edges or vertices, need to find all vertices or edges | Slow to add or remove vertices, because matrix must be resized/copied | Slow to add or remove vertices and edges, because matrix must be resized/copied |
Adjacency lists are generally preferred because they efficiently represent sparse graphs. An adjacency matrix is preferred if the graph is dense, that is the number of edges |E| is close to the number of vertices squared, |V|2, or if one must be able to quickly look up if there is an edge connecting two vertices.
Read more about this topic: Graph (abstract Data Type)