Big O in Adjency List - remove vertex and remove edge(time complexity cost of performing various operations on graphs)

Question

I have to prepare explanation of time complexity of removing vertex (O(|V| + |E|)) and edge (O(|E|)) in Adjency List.

When removing vertex from graph with V vertices and E edges we need to go through all the edges (O(|E|)), of course, to check if which ones need to be removed with the vertex, but why do we need to check all vertices?

I don't understand why in order to remove edge we need to go through all the edges. I think I might have bad understanding from the beginning, so would you kindly help with those two above?

Answer 1

To remove a vertex, you first need to find the vertex in your data structure. This time complexity of this find operation depends on the data structure you use; if you use a HashMap, it will be O(1); if you use a List, it will be O(V).

Once you have identified the vertex that needs to be removed, you now need to remove all the edges of that vertex. Since you are using an adjacency List, you simply need to iterate over the edge-list of the vertex you found in the previous step and update all those nodes. The run-time of this step is O(Deg(V)). Assuming a simple graph, the maximum degree of a node is O(V). For sparse graphs it will be much lower.

Hence the run-time of removeVertex will only be O(V).

Answer 2

Consider a graph like this:

A -> A
A -> B
A -> C
A -> D
B -> C

The adjacency list will look like this.

A: A -> B -> C -> D -> NULL
B: C -> NULL
C: NULL
D: NULL

Let's remove the vertex C, we have to go through all edges to see if we need to remove that edge, that's is O(|E|) Otherwise - how do you find A->C need to be removed?. After then, we need to remove the list C: NULL from the top level container. Depending on the top level container you may or may not need O(|V|) time for this. For example, if the top level container is an array and you don't allow holes, then you need to copy the array. Or the top level is a list, you will need to scan through the list to find the node representing C to delete.

From the original graph, let's removing the edge A->D, we have to go through the whole linked list A -> B -> C -> D to find out the node D and remove it. That's is why you need to go through all vertices. In the worse case, a vertex connects to all other vertices, so it need to go through all vertices to delete that element, or O(|V|). Depending on your top level container, again, you may or may not be able to find the list fast, that will cost you another O(|V|), but in no case I can imagine removing an edge that O(|E|) in an adjacency list representation.