Big O in Adjency List - remove the top and remove the edge (time spent on various operations on the charts)

Question

I need to prepare an explanation of the time complexity of deleting the vertex ( O(|V| + |E|)) and edge ( O(|E|)) in the address list.

When removing vertices from a graph with V vertices and E edges, we must, of course, go through all the edges ( O(|E|)) to check whether they need to be deleted using the vertex, but why do we need to check all the vertices ?

I don’t understand why we need to go through all the edges to remove the edge. I think that from the very beginning I would have a bad understanding, so that you would kindly help with the two above?

Answer 1

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

Once you have identified the vertex that you want to delete, now you need to delete all the edges of this vertex. Since you are using an adjacency list, you just need to iterate over the extreme list of vertices found in the previous step and update all of these nodes. The time taken to complete this step O(Deg(V)). Assuming a simple graph maximum degree of a node is O(V). For sparse graphs, it will be much lower.

Consequently, runtime removeVertexwill be only O(V).

Answer 2

:

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

.

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

C, , , , O (| E |). - A- > C ?. C: NULL . O (| V |) . , , , . - , , node, C .

, A- > D, A → B → C → D, node D . . , , O (| V |). , , O (| V |), , O (| E | ) .