why the time complexity in many operations in grahs depend on edges why not only vertices whatis the meaning of having edges jn time complexity?
Time complexity in graphs
Hello @Namanjain123
The complexity depends on the number of edges in a graph because many a times we have problems which requires traversal of all the edges.
Let a question be, given a weighted graph, print out the sum of all the edge weights.
So the time taken here will be proportional to the number of edges only.
Another question can be, given a graph without loops where each vertex has some value inside it, replace each vertex by the sum of the of it child vertex values.
Let the vertices be 10 and edges be 40 so here also you need to traverse each edge to see the connections (which is the parent, which is the child)
NOTE:-
In a graph with v vertices we can have a maximum of vC2 edges = ((v)(v-1))/2 edges (Excluding self loops).
(which is nearly v^2 edges)
Also NOTE:-
That there are two representations of a graph
- Adjacency List representation
- Adjacency Matrix representation
If you use the ALR then you use some data structure like a list and then you store only the edges that are present, so here the complexity is more likely to be in form of number of edges
While if you use AMR then you mark edges in a matrix, if an edge is NOT present then you make that cell -1
To perform a search for edges which are present in the graph you need to traverse the whole matrix, so here the complexity is more likely to be in form of number of vertices (because max edges = V^2).
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.