3.6 Directed Acyclic Graphs and topological Ordering

If a directed graph has no cycles, it's called a Directed Acyclic Graph(DAG). DAGS can be used to implement dependencies or precedence relations and are widely used in Computer Science.For instance, we can have a set of tasks {1, 2, 3,…, n} to be performed, the condition being that for certain tasks i and j, i must be performed before j. Each task is represented by a node, and there is an edge from i to j if i must be performed before j. In this kind of relation, the resulting graph must a DAG since there must be a task that is performed first, otherwise we would have a cycle which would mean that no task could ever be done.A topological ordering is an order in which the tasks could be performed so that all dependencies are respected. In other words, for every edge (v_i , v_j), we have i < j and all edges point forward in the ordering. Thus, in a topological order, whenever we come to a task v_j, all the tasks preceding v_j have already been performed. If G has a topological ordering, then G is a DAG. The main problem we have when dealing with a DAG is to find the efficiency of the algorithm that finds its topological ordering.

The first node v₁ in a topological order doesn't have any incoming edge.Every DAG has a node with no incoming edges.
In addition, if G is a DAG, then G has a topological ordering.

Algorithm * »»»To computer a topological ordering on G: »»»»Find a node v with no incoming edges and order it first »»»»» Delete v from G »»»»»» Recursively compute a topological ordering G-{v} »»»»»»»>and append this order after v