Topological Sort
Topological sort orders the nodes in a graph by their dependencies.
Mental model for the name
We meet topology when we talk about network setup. It means the logical structure of the network.
The same applies here. We sort the nodes by the structure of the graph.
Not a regular sort
Topological sort doesn't order elements by value, like Insertion Sort, Bubble Sort, or Merge Sort.
Topological sort needs two important components
- Adjacency list - List of outgoing connections from a node.
- In-degree - the number of incoming connections for a node.
Contents of Adjacency list and In-degree
The adjacency list holds the actual node names. The in-degree holds only the count.
Kahn's Algorithm
Using actual values versus Node IDs
You can sort a graph topologically using the node values, which are strings. This solution uses maps.
In programming tests, the node values are squeezed to integers 0 to N. Then you just use arrays, since the array index is the node value.