Topological sort in linear time?
I have read several places that claim that it is possible to do topological sorting in linear time. One such statement is made here - they say - O (V + E) http://en.wikipedia.org/wiki/Topological_sorting
But they have: there is for each inside the while loop. I think it does O (n ^ 2).
Then I found this solution - https://courses.cs.washington.edu/courses/cse326/03wi/lectures/RaoLect20.pdf - in slide 19 - assuming they are looking for a faster way - but in the second step Step 3 , they look for all neighboring nodes (inside the while loop), so it does O (n ^ 2) as well.
So this case is http://www.geeksforgeeks.org/topological-sorting/
What am I missing here?
source to share
has an a for each inside the while loop. I think it does O (n ^ 2).
If you are using the adjacency list view of your graph, you look at each edge exactly once in the inner loop, so O (max {n, m}) = O (n + m).
Of course, it's also O (n ^ 2), but it's not a tight upper bound.
they look for all neighboring nodes (inside the while loop), so it does O (n ^ 2) too.
Again, this is also O (n + m) if you are using adjacency lists to represent your graph.
source to share