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

Directed Acyclic Graphs Examples and Algorithm

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

directed acyclic graphs examples
  • 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
directed acyclic graphs examples
  • 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.

READ MORE

Algorithms related posts visit HERE

Data Structures related posts visit HERE

Databases related posts Visit HERE

Python-related posts Visit HERE

C++ related posts Visit HERE

Data Science related posts visit HERE