Topological Sort

A topological sort is an ordering of the nodes of a directed graph such that if there is a path from node $u$ to $v$, then node $u$ appears before node $v$ in the ordering.

• An order of the vertices such that all the edges go forward

A topological sort does NOT exist if there are cycles! It would violate the definition.

Extra Note: However, we kind of use this idea to check Strong Connectivity in Kosaraju’s Algorithm, but we just make sure that it has not been visited before doing Depth-First Search.

Building Topological ordering

There are few ideas.

1. Keep count of the indegrees of the node, and then process the nodes from lowest to highest indigree

Also used for Backpropagation, to decide the order to visit the vertices

def backward(self):
	topo = []
	visited = set()
	def build_topo(v):
		if v not in visited:
			visited.add(v)
			for child in v._prev: # these are the children of the node
				build_topo(child)
			topo.append(v)
	build_topo(self)
	self.grad = 1.0
	for node in reversed(topo):
		node._backward()

I am confused

Consider this graph. We can find a topolgical ordering A → B → C → D, and there still is a cycle. As long as we don’t use the D→A edge. SAC ‘22 Code Challenge 5 Junior P4. In that example, they just let you assume that there are no cycles. However, you actually need to check for yourself if you truly want to find a topological order. That is an edge case.

Algorithm for finding order of DAG

The idea is to go through the nodes of the graph and always begin a depth-first search at the current node if it has not been processed yet. Only when the node is done being processed that we add it to order.

int N; // number of vertices
int adj[N][N];
bool visited[N];
vector<int> order;
 
void dfs(int v) {
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u]) {
            dfs(u);
        }
    }
    order.push_back(v);
}
 
void topological_sort() {
    memset(visited, false, sizeof(visited));
    order.clear();
    for (int i = 0; i < n; ++i) {
        if (!visited[i])
            dfs(i);
    }
    reverse(order.begin(), order.end()); // Ans gives the topological ordering
}

Examples of problems I have encountered:

•  SAC ‘22 Code Challenge 5 Junior P4
  • OMG, super interesting insight from this problem. The topological sort of reverse edges is the same as reversing topological sort results. And that is why my implementation here works.

Dynamic Programming

Don’t think of topological sort in DP as going forwards or backwards. It is just the order in which the problem can be solved. Think of the dependencies.

And all DP problems need to have a topological sort, else you end up with just an infinite loop.

Luckily, most DP problems we see follow a rather simple order, either forwards from 0 to n or backwards from n to 0.