Overview
This post summarizes adjacency lists and adjacency matrices, which are data structures used to represent graphs.
Both adjacency lists and adjacency matrices can be used for directed and undirected graphs.
Adjacency List
An adjacency list is a data structure where each vertex (node) maintains a list of its adjacent vertices.
Time Complexity
- Space complexity: O(V+E) (V: number of vertices, E: number of edges)
- Finding adjacent vertices of a specific vertex: O(1)
- Checking the existence of a specific edge: O(degree) (degree: number of adjacent edges)
- Enumerating all adjacent vertices for all vertices: O(V+E)
Adjacency lists are efficient for graphs with fewer edges.
Implementation
The source code is available at adjacency_list.
Adding edges is a bit complex in this implementation.
Adjacency Matrix
An adjacency matrix is a data structure that represents connections between vertices (nodes) as a 2D matrix.
The presence of an edge between vertices is represented using values of 0 or 1.
Time Complexity
- Space complexity: O(V^2)
- Finding adjacent vertices of a specific vertex: O(V)
- Checking the existence of a specific edge: O(1)
- Enumerating all adjacent vertices for all vertices: O(V^2)
Adjacency matrices are efficient for graphs with many edges or when frequent edge existence checks are required.
Implementation
The source code is available at adjacency_matrix.
The conditions for adding edges might seem slightly tricky in this implementation.