0
$\begingroup$

Topological sorting on a graph seems like an immensely powerful operation:

No matter whether the algorithm ends in success or failure, we obtain an important information about the topology of the graph, i.e. whether it is cyclic or not.
If it ends in failure, we can trivially find the cycle that let the algorithm end in failure, and if it succeeds, we get a working linear ordering on the graph.
And all that is possible in asymptotic linear time!
(It's in $\mathcal O (n+m)$; $n,m$ are the vertices and edges of the graph)

While I've seen the proofs and algorithms, and yes, it works, it still baffles me how exactly this is possible.

Looking at another way, a topological sorting a combination of all partial orders of the graph into a single linear order, which still maintains all the original partial orders. So e.g. even if we're given a set of partial orders, we'd still turn it into a graph, and probably be faster than any alternative.

Why exactly is topological sorting so fast?


I think I've found an answer that suffices for me.
Generally, I'd say the complexity of an algorithm derives from the diversity of possible inputs and the structure properties (constraints) that you have to take care of.

Graphs are insanely diverse, the range of problems they can be applied to alone shows this. And then, a graph has quite a lot of structure as well. So, unless you can somehow abuse its structure, I'd think problems on graphs would be fairly difficult.

However, for the algorithm, we can use the structure property that every acyclic graph has a node with no incoming edges. So, instead of having to care about the whole graph, we just have to observe it locally. As therefore the topology of the graph as whole turns irrelevant, the diversity of graphs (that we care about) greatly diminishes as well, and thus we achieve such a high time efficiency.

I guess what had put me off so much was that the statement that makes all this possible is so simple (and easy to deduce).

$\endgroup$
  • $\begingroup$ I think asking why it's so fast would be like asking why is binary search so fast? So fast compared to what? You should also remember that $O(m + n) = O(n^2)$ in the worst case, so in terms of sorting... it's not really that fast especially when you're looking at a total order (e.g. sorting numbers). Topological sort is essentially the equivalent of a non-transitive sorting algorithm, where you can't infer, in the worst case I may need to check $x_1$ against all other $x_2 \ldots x_n$, and how it compares might not tell me anything about how $x_2$ compares to all other $x_3 \ldots x_n$. $\endgroup$ – ryan Jun 14 '18 at 2:38
  • $\begingroup$ @ryan Why $O(n^2)$? Shouldn't it be more along the lines $O(m+n) = O(max(m,n))$? $\endgroup$ – Sudix Jun 14 '18 at 2:59
  • 1
    $\begingroup$ Yes, but $m = O(n^2)$ in the worst case, a directed edge between every pair of nodes. $\endgroup$ – ryan Jun 14 '18 at 3:07
  • $\begingroup$ @ryan Ah, thanks. Well, especially in that edge case that the time complexity is $O(n^2)$, it's e.g. a whole lot faster than if we'd consider every possible path, and use them to obtain a linear ordering. (While there is an algorithm that has to check every element only twice or so, we just got so many possible paths. The graph however gets rid of the redundancy that the paths would contain) $\endgroup$ – Sudix Jun 14 '18 at 3:33
  • $\begingroup$ I'm not quite sure what you mean. It is certainly faster than brute force. Could you possibly reword you question and get more specific? Answering why it's so fast, because we simply have an algorithm that can run that fast to solve the problem. $\endgroup$ – ryan Jun 14 '18 at 4:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.