Directed Acyclic Graphs Examples

In this post we are going to talk about Directed Acyclic Graphs Examples and Topological order in a graph.

Directed Acyclic Graphs?

Def. A Directed Acyclic Graph is is a directed Graph which contain no directed cycles. Definition of Directed Graphs HERE.

Lemma. If a graph is Directed Acyclic then G has a node with no entering edges.

Topological Order Def. A topological order of a directed graph is G = (V,E) is an ordering of its nodes as V1 to Vn so that for every edge (Vi, Vj) we have i < j.

Lemma. If a graph G is Directed Acyclic then it has Topological Ordering.

Directed Acyclic Graphs Examples and Algorithm

Suppose We have a Directed Acyclic Graph(image below) and we have to find its topological ordering.

• First Find out all the nodes which do not have any incoming edges.
• In our Graph(above image) there are two nodes having no incoming edges, Node V1 and Node V2.
• Remove node V1 or V2 from the graph and put it in Topological Ordering.
• In my case I removed V1, so Topological Ordering is : V1
• Then remove V2, Now Topological Ordering is : V1, V2
• The graph becomes:
• Now look for Nodes which don’t have any incoming edges in my case it is V3.
• Remove V3 from graph and put it into the topological Ordering
• Topological Ordering: V1, V2 , V3 and Graph becomes
• Again do the same thing until you are left with No nodes.
• I go the Topological Ordering: V1, V2, V3, V4, V5, V6, V7

The time Complexity for this algorithm is O(m + n) , where m is number of nodes and n is number of edges.