Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Topological sort in linear time?

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?

like image 905
ND27 Avatar asked Aug 31 '14 20:08

ND27


People also ask

What is the time complexity of topological sorting?

Topological Sort Time Complexity The time complexity of topological sort using Kahn's algorithm is O(V+E), where V = Vertices, E = Edges.

Is topological sort linear?

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.

What is topological sort explain with example?

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.

What is topological sort in algorithm?

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.


1 Answers

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.

like image 185
Niklas B. Avatar answered Nov 15 '22 05:11

Niklas B.