Store a graph as one list per vertex holding its neighbours. Memory grows with the edges that actually exist, O(V + E), and listing a vertex’s neighbours costs only its degree.
- Typical operation
- O(deg(v))
- Space
- O(V + E)
Store a graph as one list per vertex holding its neighbours. Memory grows with the edges that actually exist, O(V + E), and listing a vertex’s neighbours costs only its degree.