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 **V**1 to **V**n so that for every edge (**V**i, **V**j) 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
**V**1 and Node**V**2. - Remove node
**V**1 or**V**2 from the graph and put it in Topological Ordering. - In my case I removed
**V**1, so**Topological Ordering is : V1** - Then remove
**V**2, 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
**V**3. - Remove
**V**3 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.

#### 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**