How to Perform Topological Sorting on a Directed Acyclic Graph

Topological sorting produces an ordering of all nodes in a Directed Acyclic Graph such that for every directed edge from node A to node B, node A appears before node B in the result. It is used to resolve dependencies, like determining the order to take courses or build software modules.

The In-Degree of a node is the count of directed edges pointing into it. A node with an In-Degree of zero has no dependencies and is ready to be processed first. This is the key insight behind Kahn's Algorithm.

Represent the graph as an adjacency list. Go through every edge in the graph. For each edge from A to B, increment the In-Degree of node B by one. After processing all edges, every node has an accurate count of how many nodes must come before it.

Go through all nodes and add every node whose In-Degree is zero to a Queue. These nodes have no prerequisites and can be processed immediately.

Start a loop that continues as long as the queue is not empty. Dequeue a node from the front and add it to your result list. This node is now considered processed and placed in its correct position in the topological order.

For the node you just processed, go through all its outgoing neighbors. For each neighbor, reduce its In-Degree by one because one of its dependencies has now been fulfilled. If any neighbor's In-Degree drops to zero, add it to the queue immediately because it is now ready to be processed.

When the loop finishes, check if the result list contains all nodes in the graph. If it does, you have a valid topological order. If the result list is smaller than the total number of nodes, it means a cycle exists in the graph and a topological sort is impossible. Return the result list or an error accordingly.