| Adjacency list | Adjacency matrix | Incidence matrix | |
|---|---|---|---|
| Store graph | |||
| Add vertex | |||
| Add edge | |||
| Remove vertex | |||
| Remove edge | |||
| Query: are vertices x and y adjacent? | |||
| Remarks | Slow to remove vertices and edges, because it needs 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 |
Graph 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.
- 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 basic operations provided by a graph data structure G usually include:
adjacent(G, x, y): tests whether there is an edge from the vertices x to y;neighbors(G, x): lists all vertices y such that there is an edge from the vertices x to y;add_vertex(G, x): adds the vertex x, if it is not there;remove_vertex(G, x): removes the vertex x, if it is there;add_edge(G, x, y): adds the edge from the vertices x to y, if it is not there;remove_edge(G, x, y): removes the edge from the vertices x to y, if it is there;get_vertex_value(G, x): returns the value associated with the vertex x;set_vertex_value(G, x, v): sets the value associated with the vertex x to v.
Structures that associate values to the edges usually also provide:
get_edge_value(G, x, y): returns the value associated with the edge (x, y);set_edge_value(G, x, y, v): sets the value associated with the edge (x, y) to v.
