Scribd
Upload
37 views5 pages

Topological Sort: Examples and Applications

The document discusses topological sorting of directed acyclic graphs (DAGs). It provides examples of topological sorting for sample DAGs and lists some applications of topological sorting like job scheduling and data serialization. It also includes a practice problem on finding the number of possible topological orderings for a given DAG and working through the steps to determine the orderings.

Uploaded by

Sakshi More
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
37 views5 pages

Topological Sort: Examples and Applications

The document discusses topological sorting of directed acyclic graphs (DAGs). It provides examples of topological sorting for sample DAGs and lists some applications of topological sorting like job scheduling and data serialization. It also includes a practice problem on finding the number of possible topological orderings for a given DAG and working through the steps to determine the orderings.

Uploaded by

Sakshi More
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Topological Sort-

It is important to note that-


Topological Sorting is possible if and only if the graph is a Directed Acyclic Graph.
There may exist multiple different topological orderings for a given directed acyclic graph.
Topological Sort Example-
Consider the following directed acyclic graph-

For this graph, following 4 different topological orderings are possible-

 123456
 123465
 132456
 132465
Applications of Topological Sort-

Few important applications of topological sort are-


 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:
Find the number of different topological orderings possible for the given graph-

Solution-
The topological orderings of the above graph are found in the following steps-
Step-01:
Write in-degree of each vertex-
Step-02:

 Vertex-A has the least in-degree.


 So, remove vertex-A and its associated edges.
 Now, update the in-degree of other vertices.

Step-03:
Vertex-B has the least in-degree.
 So, remove vertex-B and its associated edges.
 Now, update the in-degree of other vertices.
Step-04:
There are two vertices with the least in-degree. So, following 2 cases are possible-
In case-01:
 Remove vertex-C and its associated edges.
 Then, update the in-degree of other vertices.
In case-02,
 Remove vertex-D and its associated edges.
Then, update the in-degree of other vertices.
Step-05:
Now, the above two cases are continued separately in the similar manner.
In case-01,
 Remove vertex-D since it has the least in-degree.
 Then, remove the remaining vertex-E.
In case-02,
 Remove vertex-C since it has the least in-degree.
 Then, remove the remaining vertex-E.

Conclusion-

For the given graph, following 2 different topological orderings are possible-
 ABCDE
 ABDCE

You might also like