Topological sort of a directed acyclic graph [DAG] is partial ordering of its nodes such that U < V implies there must not exist a path from V to U.
Kahn’s algorithm I implemented, instead produces a linear ordering such that […, U, …, V, …] means there may be a path from U to V, but not vice versa.
Partial ordering is very useful in many situations. One of them arises in parallel computing where a program can be represented as DAG.
E = (A + B) * (C - D)
Each node represents an operation and directed links in between are their dependencies.
There are 8 operations [including fetch and store] in this expression, but modern super-scalar CPUs are able to execute some operations in parallel to reduce the execution time up to 4 steps.
We have already discussed about the relationship between all four types of edges in the DFS. Below is the relation we have seen between the departure time for different types of edges involved in a DFS of directed graph-
Tree edge (u, v): departure[u] > departure[v]
Back edge (u, v): departure[u] < departure[v]
Forward edge (u, v): departure[u] > departure[v]
Cross edge (u, v): departure[u] > departure[v]
As we can see that for a tree edge, forward edge or cross edge (u, v), departure[u] is more than departure[v]. But only for back edge the relationship departure[u] < departure[v] is true. So it is guaranteed that if an edge (u, v) has departure[u] > departure[v], it is not a back-edge.
We know that in DAG no back-edge is present. So if we order the vertices in order of their decreasing departure time, we will get topological order of graph (every edge going from left to right).
