Intro to DBMS

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.
In-degree: Number of vertices incoming toward a edge is called its in-degree.

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