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

Правка en1, от 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?

Теги graphs, algorithm complexity

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский motatoes 2018-01-12 18:50:28 1180 Initial revision (published)