**Topological Sort**

Topological Sort is a linear-ordering of the vertices.

**According to topological sort**

“if there is an edge in the diagram going from vertex ‘A’ to vertex ‘B’, then ‘A’ comes before than ‘B’ in the ordering”.

**Important Note**

- Topological Sorting can be applied if and only if the graph is a Directed Acyclic Graph.
- For a single directed acyclic graph there may exist more than one ordering sequences.

**Steps to find the Topological Ordering**

- First, find the vertex which having the least in-degree.
- Second Remove the least in-degree vertex along with its associated edges
- Update the in-degree of rest of vertices.
- Interlink the all the removing (least in-degree) vertices in the order as they removed from directed acyclic graph.

**Example:**

Find the all possible topological orderings for the given directed acyclic graph

**Solution:**

**Step-01: **Write in-degree of each vertex

**Step-02: **As vertex-A holds least in-degree so remove it along with its associated edges and update the rest of graph

**Step-03:** As vertex-B holds least in-degree so remove it with its associated edges and update the rest of graph

**Step-04: **There are two vertices with the similar least in-degree. So there are two cases are possible

**Case-01**

- Remove vertex-C before vertex-D

**Case 02**

- Remove vertex-D before vertex-C

Above both cases are valid, as given under

**Step-05:** Now, the above two cases will run separately parallel.

**In case 01:**

As vertex-D holds least in-degree so remove it with its associated edges

As the Last vertex-E is separated already by separating second-last vertex-D.

**In case-02:**

As vertex-C holds least in-degree so remove it with its associated edges

**Step 06: **As the Last vertex-E is separated already by separating second-last vertex-C. So attach E in the last of on-going ordering.

**Conclusion**

For the given directed acyclic graph, following two different topological orderings are possible

- A→B→C→D→E
- A→B→D→C→E