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.