Complexities of Graph Operations
Let's discuss the performance of the two graph representation approaches.
We'll cover the following
Time Complexities #
Below, you can find the time complexities for the 4 basic graph functions.
Note, that in this table V means the total number of vertices and E means the total number of edges in the Graph.
| Operation | Adjacency List | Adjacency Matrix |
|---|---|---|
| Add Vertex | O(1) | O(V2) |
| Remove Vertex | O(V+E) | O(V2) |
| Add Edge | O(1) | O(1) |
| Remove Edge | O(E) | O(1) |
Adjacency List #
-
Addition operations in adjacency lists take constant time as we only need to insert at the head node of the corresponding vertex.
-
Removing an edge takes O(E) time, because in the worst case, all the edges could be at a single vertex and, hence, we would have to traverse all E edges to reach the last one.
-
Removing a vertex takes O(V + E) time because we have to delete all its edges and then reindex the rest of the list one step back in order to fill the deleted spot.
Adjacency Matrix #
-
Edge operations are performed in constant time as we only need to manipulate the value in the particular cell.
-
Vertex operations are performed in O(V2) since we need to add rows and columns. We will also need to fill all the new cells.
Comparison #
Both representations are suitable for different situations. If your model frequently manipulates vertices, the adjacency list is a better choice.
If you are dealing primarily with edges, the adjacency matrix is the more efficient approach.
Keep these complexities in mind because they will give you a better idea about the time complexities of the several algorithms we’ll see in this section.
In the next lesson, we will look at a special type of graph called the bipartite graph.
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.