Graph (Adjacency list)
One of the two main graph implementations. This contains a collection of unordered lists where each list contains all the connected neighbors to a vertex.
| Pros | Cons |
|---|---|
| Efficient for a sparse dataset | Non-optimal to determine if a node is a neighbor |
| Efficient to find all neighbors of a vertex |
Implementations
Python: Custom implementation
graph = [[1, 2], [2], []]
| Operations | Worst | Average |
|---|---|---|
| Add edge | O(1) | |
| Add vertex | O(1) | |
| Are two vertexes adjacent? | O(|V|) | |
| Create graph | O(|V|+|E|) | |
| Remove edge | O(|V|) | |
| Remove vertex | O(|E|) |
