Time complexities in graph

#1

why time complexities in graph depends on edges why not onle vertices/nodes

#2

@Namanjain123 Let me explain in terms of BFS and DFS.
Now when an adjacency list is used then, DFS and BFS have complexity O(V+E), and if an adjacency matrix is used, the complexity is O(V2). Why is this that in one cases only vertices matter and in the other both matter?

In both cases, the runtime depends on how long it takes to iterate across the outgoing edges of a given node. With an adjacency list, the runtime is directly proportional to the number of outgoing edges. Since each node is visited once, the cost is the number of nodes plus the number of edges, which is O(m + n). With an adjacency matrix, the time required to find all outgoing edges is O(n) because all n columns in the row for a node must be inspected. Summing up across all n nodes, this works out to O(n2).

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.