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).