I read a few places which claim that its possible to do topological sort in linear time. One such claim is made here - They say - O(V+E) http://en.wikipedia.org/wiki/Topological_sorting
But the algo they have : has a for each inside a while loop. I think that makes it O(n^2) instead.
Then I found this solution - https://courses.cs.washington.edu/courses/cse326/03wi/lectures/RaoLect20.pdf - on slide 19 - apparantly they are looking for a faster way - but on second step of Step 3, they are looking for all adjacent nodes (inside a while loop), so that makes it O(n^2) too.
So is this case - http://www.geeksforgeeks.org/topological-sorting/
What am I missing here?
Topological Sort Time Complexity The time complexity of topological sort using Kahn's algorithm is O(V+E), where V = Vertices, E = Edges.
A topological sort is a linear ordering of vertices in a directed acyclic graph (DAG). Given a DAG G = (V, E), a topological sort algorithm returns a sequence of vertices in which the vertices never come before their predecessors on any paths.
The topological sort algorithm takes a directed graph and returns an array of the nodes where each node appears before all the nodes it points to. The ordering of the nodes in the array is called a topological ordering. Here's an example: Since node 1 points to nodes 2 and 3, node 1 appears before them in the ordering.
Topological Sorting or Kahn's algorithm is an algorithm that orders a directed acylic graph in a way such that each node appears before all the nodes it points to in the returned order, i.e. if we have a --> b, a must appear before b in the topological order.
has a for each inside a while loop. I think that makes it O(n^2) instead.
If you use an adjacency list representation of your graph, you look at every edge exactly once in the inner loop, so it's O(max {n, m}) = O(n + m).
Of course it is also O(n^2), but that is not a tight upper bound.
they are looking for all adjacent nodes (inside a while loop), so that makes it O(n^2) too.
Again, it's also O(n + m) if you use adjacency lists to represent your graph.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With