DBMS Notes

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

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

Help Other’s By Sharing…

Contact Us

Burewala, Vehari, Punjab, Pakistan

cstaleem1@gmail.com

Website: CStaleem.com

Pin It on Pinterest