So from what I understand, a Topological sort, on a DAG, is simply a DFS. Given this question,
our job is to arrange n ill-behaved children in a straight line, facing front. You are given a list of m statements of the form “i hates j”. If i hates j, then you do not want put i somewhere behind j, because then i is capable of throwing something at j.
Give an algorithm that orders the line, (or says that it is not possible) in O(m + n) time.
Solution:
We can save us a lot of time if we model the problem correctly.
In this example 1 hates 2 and 3, 2 hates 4, 3 hates 4, and 4 hates 5. You can see that we can use topological sorting for this problem which is also described early in the book. Image of the graph:
http://blog.panictank.net/wp-content/uploads/2012/01/5-23a.png
I don't understand how simply do a DFS answers the question. an Explanation would help. I tried reading the wikipedia page; I just fail to see the relation. I know in general, in topological sort, x–>y implies job x must be done before y, but my initial misconception still remains.
Best Answer
If you do a depth first search (in the directed graph), and record the finish time $f[u]$ of each vertex $u$, then the topological sorted list is the list of vertices, sorted in the order of descending $f[u]$. Recall that if the graph is acyclic and if there is a path from $u$ to $v$, then $f[u] \gt f[v]$ (children finish before their parents).
Now if you form a graph with vertices as the children and a directed edge from $i$ to $j$ iff $j$ hates $i$. If there is a cycle in the graph, the ordering is not possible, otherwise the graph is a directed acyclic graph (DAG in short) and an ordering is possible.
Say you do a DFS (starting from a dummy node which has a directed edge to all vertices) and record the finish times. Now given two vertices $i$ and $j$, if $i$ hates $j$, then you will have that $f(j) \gt f(i)$, and your topologically sorted list will place $j$ before $i$.