Topological Sorting

Explain what topological sorting is and how it is implemented.

What is topological sorting?

Topological sorting is used only on Directed Acyclic Graphs(DAG) and is used to produce a linear ordering of vertices such that for all edges (u, v), u always appears before v. The result is not always unique.

Quick Solution

1. The first step is to identify a node that has an in-degree of 0, there can be multiple. If there are none in the graph, then the graph has cycles.
2. After identifying a node with an in-degree of 0, the node, and all of its outgoing edges should be removed.
3. Repeat steps 1 and 2 until the graph is empty.

In-Depth Solution

Pseudocode for Topological Sort

1. The function should take in one parameter being the directed acyclic graph.
2. Generate a vector that contains the in-degree of all vertices in the graph.
3. While the graph still has vertices do the following
4. Get the next vertex with an in-degree of 0. Let it be called U.
5. Remove U and its outgoing edges from the graph.
6. Set in_degree_vector[u] to -1 to show that it has been removed from the graph.
7. Repeat steps 4–6 until the graph is empty.

Further Reading

Topological Sorting - GeeksforGeeks

Topological Sorting