Блог пользователя motatoes

Автор motatoes, история, 7 лет назад, По-английски

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?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Assuming that explore(v) runs a simple DFS/BFS, which has complexity O(|V| + |E|), if we run explore(v) for every vertex v, then we have a complexity of O(|V|(|V| + |E|)) which is O(|V|2 + |V||E|)