Graph (Adjacency matrix)
One of the two main graph implementations. This is a matrix that indicates whether pairs of vertices are in the graph.
| Pros | Cons |
|---|---|
| Constant time to determine if a node is a neighbor | Inefficient to find all neighbors of a vertex |
| Inefficient to add/remove vertices |
Implementations
Python: Custom implementation
graph = [[0, 1, 1], [0, 0, 1], [0, 0, 0]]
| Operations | Worst | Average |
|---|---|---|
| Add edge | O(1) | |
| Add vertex | O(|V|^2) | |
| Are two vertexes adjacent? | O(1) | |
| Create graph | O(|V|^2) | |
| Remove edge | O(1) | |
| Remove vertex | O(|V|^2) |
