**Topological Sort Examples**

Topological Sort examples provide the 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 ‘B’ in the ordering”.

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

**Keep in mind that a directed Acyclic Graph is **a graph having no graph cycles and is labeled with directed arrows.

**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 the rest of the vertices.
- Interlink all the removing (least in-degree) vertices in the order as they are removed from the directed acyclic graph.

**Example of ****Topological Sort**

**Problem:** Find 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 the least in-degree, remove it along with its associated edges and update the rest of the graph

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

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

**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 the least in-degree, remove it with its associated edges

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

**In case-02:**

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

**Step 06: **As the Last vertex-E is separated already by separating the second-last vertex-C. So attach E to the last part of the ongoing ordering.

**Result:**

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

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