Get the latest tech news

Adjacency Matrix and std:mdspan, C++23

In graph theory, an adjacency matrix is a square matrix used to represent a finite (and usually dense) graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not, and in weighted graphs, they store the edge weights. In many beginner-level tutorials, adjacency matrices are implemented using vector of vectors (nested dynamic arrays), but this approach has inefficiencies due to multiple memory allocations.

In this blog post, we’ll explore various implementations of an adjacency matrix, starting with a basic approach and progressively improving it using std::mdspan. Instead, we can use a single contiguous vector to store the matrix elements, which improves cache locality and reduces memory fragmentation. explicit ctor - to prevent unwanted conversions noexcept- at least in some basic functions nodiscard- to indicate that a return value should be used, not just thrown away error handling through exceptions

Get the Android app