Graph representations
programming
How we represent a directed graph or undirected graph in an algorithm can effect the run time of an algorithm.
Bellow are some common ways to do this:
| Data structure | Space complexity | Time to check connection | Time to find neighbours |
|---|---|---|---|
| Adjacency list | $O(\vert V \vert + \vert E \vert)$ | $O(N_v)$ | $O(N_v)$ |
| Adjacency matrix | $O(\vert V \vert^2)$ | $O(1)$ | $O(\vert V \vert)$ |
| Edge list | $O(\vert E \vert)$ | $O(\vert E \vert)$ | $O(\vert E \vert)$ |