Graphs are an integral part of computer science. Mastering them is necessary to become an accomplished software developer. Here is the data structure analysis of graphs:
Node/Edge Management | Storage | Add Vertex | Add Edge | Remove Vertex | Remove Edge | Query |
---|---|---|---|---|---|---|
Adjacency List | O(|V|+|E|) | O(1) | O(1) | O(|V| + |E|) | O(|E|) | O(|V|) |
Incidence List | O(|V|+|E|) | O(1) | O(1) | O(|E|) | O(|E|) | O(|E|) |
Adjacency Matrix | O(|V|^2) | O(|V|^2) | O(1) | O(|V|^2) | O(1) | O(1) |
Incidence Matrix | O(|V| ⋅ |E|) | O(|V| ⋅ |E|) | O(|V| ⋅ |E|) | O(|V| ⋅ |E|) | O(|V| ⋅ |E|) | O(|E|) |