How is the complexity of this algorithm O(|v||v| + |v||E|)

Revision en1, by motatoes, 2018-01-12 18:50:28

Hi CF

I'm taking this course on coursera called "algorithms on graphs". In these slides there is a description of a naive algorithm for calculating strongly connected components (SCC) on a directed graph (slide number 5):

I have a question regarding the complexity of this algorithm. We know that for each vertex V we need to explore all its neighbours so I assumed that its complexity is |V|^2 if the graph is fully connected?

Then for each neibghbour of v we must check that we can reach back to V, so what will the complexity be in this case?

My question is how can we prove that the complexity of this naive algorithm is P(|V||V| + |V||E|) where |V| is the number of vertices and |E| is the number of edges?

Tags graphs, algorithm complexity

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English motatoes 2018-01-12 18:50:28 1180 Initial revision (published)