Topological Sort | Topological Sorting

Topological Sorting-

 

  • Topological Sorting of vertices of a Directed Acyclic Graph (DAG) is a linear ordering of the vertices in such a way that if there is an edge in the DAG going from vertex ‘u’ to vertex ‘v’, then ‘u’ comes before ‘v’ in the ordering.

 

Example-

Consider the following Directed Acyclic Graph-

 

 

For the given DAG, following 4 different topological orderings are possible-

  • 1 2 3 4 5 6
  • 1 2 3 4 6 5
  • 1 3 2 4 5 6
  • 1 3 2 4 6 5

 

NOTES

  • Topological Sorting is not possible if the graph is not a Directed Acyclic Graph.
  • There may exist multiple topological orderings for a Directed Acyclic Graph.

 

Applications of Topological Sort-

 

  • Scheduling jobs from the given dependencies among jobs.
  • Instruction Scheduling
  • Determining the order of compilation tasks to perform in makefiles.
  • Data Serialization

 

PRACTICE PROBLEMS BASED ON TOPOLOGICAL SORT-

 

Problem-01:

The number of different topological orderings for the graph shown is ________ ?

 

 

Solution-

 

For video solution, watch this video.

 

Step-01:

Write in-degree of each vertex-

 

 

Step-02:

 

Now, since vertex-A has least in-degree, so remove vertex-A and its associated edges and update in-degree of other vertices.

 

Step-03:

 

Now, since vertex-B has least in-degree, so remove vertex-B and its associated edges and update in-degree of other vertices.

 

 

Step-04:

 

Now, since we have two vertices with least in-degree, so we have 2 choices and therefore we have 2 cases-

Case-01: Remove vertex-C and its associated edges and update in-degree of other vertices.

Case-02: Remove vertex-D and its associated edges and update in-degree of other vertices.

 

 

Step-05:

 

Now, we will continue with the above two cases separately in the similar manner.

  • In case-01, first remove vertex-D since it has least in-degree and then remove the remaining vertex-E.
  • In case-02, first remove vertex-C since it has least in-degree and then remove the remaining vertex-E.

 

 

Thus, for the given graph, 2 different topological orderings are possible-

  1. A B C D E
  2. A B D C E

 

Problem-02:

The number of different topological orderings for the graph shown is ________ ?

 

 

Solution-

 

For video solution, watch this video.

 

Step-01:

Write in-degree of each vertex-

 

 

Step-02:

 

Now, since vertex-1 has least in-degree, so remove vertex-1 and its associated edges and update in-degree of other vertices.

 

 

Step-03:

 

Now, since we have two vertices with least in-degree, so we have 2 choices and therefore we have 2 cases-

Case-01: Remove vertex-2 and its associated edges and update in-degree of other vertices.

Case-02: Remove vertex-3 and its associated edges and update in-degree of other vertices.

 

 

Step-04:

 

Now, we will continue with the above two cases separately in the similar manner.

  • In case-01, remove vertex-3 since it has least in-degree and update in-degree of other vertices.
  • In case-02, remove vertex-2 since it has least in-degree and update in-degree of other vertices.

 

 

Step-05:

 

  • In case-01, remove vertex-4 since it has least in-degree and update in-degree of other vertices.
  • In case-02, remove vertex-4 since it has least in-degree and update in-degree of other vertices.

 

 

Step-06:

 

  • In case-01, we have 2 choices since there are 2 vertices with least in-degree. So, 2 cases are possible. We can take any of the two vertices first.
  • Same is with case-02.

 

 

Thus, for the given graph, 4 different topological orderings are possible-

  1. 1 2 3 4 5 6
  2. 1 2 3 4 6 5
  3. 1 3 2 4 5 6
  4. 1 3 2 4 6 5

 

Problem-03:

Consider the directed graph given below. Which of the following statements is true? (GATE-2014)

 

 

  1. The graph does not have any topological ordering.
  2. Both PQRS and SRPQ are topological orderings.
  3. Both PSRQ and SPRQ are topological orderings.
  4. PSRQ is the only topological ordering.

 

Solution-

 

For video solution, watch this video.

Correct Option is (C).

  • The given graph is a Directed Acyclic Graph, so there will exist topological orderings.
  • P and S must appear before R and Q in topological orderings as per the definition.

 

Problem-04:

Consider the following directed graph-

 

 

The number of different topological ordering of the vertices of the graph is ________ ? (GATE-2016)

 

Solution-

 

For video solution, watch this video.

Number of different topological orderings possible = 6

Thus, Correct answer is 6.

 

To gain better understanding of the concepts of Topological Sort,

Watch this video

To practice previous years GATE problems on Topological Sort,

Watch this video

 

Download the handwritten notes of “Topological Sort” here-

Get more notes and other study material of Design and Analysis of Algorithms (DAA).

Watch video lectures by visiting our YouTube channel LearnVidFun.

Summary
Topological Sort | Topological Sorting
Article Name
Topological Sort | Topological Sorting
Description
Topological Sorting is a linear ordering of the vertices of a Directed Acyclic Graph. Topological Sort Examples step by step. How to find different topological orderings possible of given graphs.
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-