Define topological sorting. list the two approaches of topological sorting and illustrate with examples. Or Explain Topological Sorting. Give its definition, algorithm, and applications.

Define topological sorting. list the two approaches of topological sorting and illustrate with examples. Or Explain Topological Sorting. Give its definition, algorithm, and applications

Answer:-

• Topological Sorting is a linear ordering of vertices in a directed graph (digraph) such that for every directed edge u→v, vertex u appears before vertex v in the ordering.
• Applicable only for:
  • Directed Acyclic Graphs (DAGs)
  • If the graph has any directed cycle, topological sorting is not possible.

      Need for Topological Sorting

• Used in problems where certain tasks must be done before others.
• Example: Course scheduling where some courses have prerequisites.

Algorithms for Topological Sorting

There are two main algorithms:

a. DFS-based Algorithm

• Perform Depth First Search (DFS) on the DAG.
• When a node finishes (i.e., when all its descendants are visited), push it to a stack.
• Once DFS is complete, pop all elements from the stack to get the topological order.
• Important Note:
  • If a back edge is found during DFS, the graph has a cycle, and topological sorting is not possible.

b. Source Removal (Kahn’s Algorithm)

• Repeatedly:
  1. Select a vertex with no incoming edges (called a source).
  2. Remove it from the graph along with its outgoing edges.
  3. Add it to the final ordering.
• Continue until:

• All vertices are removed → Topological order found.
• No source remains → Graph has a cycle → Not possible.

    Properties

• A DAG can have more than one valid topological ordering.
• Both algorithms produce correct results.
• DFS and Source Removal may return different valid orders.

Other practice problems….
Apply the DFS-based algorithm to solve the topological sorting problem for the following digraphs: