Topological Ordering

Topological ordering

Definition: Suppose $G=(V,E)$ is a DAG. A topological order is an ordering < of $V$ such that for any edge $(v,w)$, we have $v<w$.

No such order if there are cycles

Number of Paths in a DAG: Given a directed acyclic graph G, and a vertex s ∈ G, give an algorithm that find the number of paths between s and every other vertex v ∈ G.

Solution: Perform a topological sort on G, and suppose the order is v1 < v2 < · · · < vn and suppose $s=vk$. For every $v_i$ with $i\le k$,the number of paths $n(i)$ is 0. For every $v_i$ with $i>k$,we consider all incoming edges $(vj,vi)$, and set $n(v_i)$ to be the sum of $n(v_j)$ for all such $j$. Both the above step, and the topological sort can be done in time $O(m+n)$.

Why use topological sort?

• Performing a topological sort on a directed acyclic graph (DAG) is a crucial step in efficiently finding the number of paths between a given source vertex $s$ and every other vertex $v$ in the graph.
• Topological sorting arranges the vertices of a DAG in a linear order such that for every directed edge $(u,v)$, vertex $u$ comes before vertex $v$ in the ordering.
• This ordering is essential because it respects the dependencies between vertices. If there is a path from $u$ to $v$, $v$ will appear after $u$ in the topological order.

Topological sorting can be performed in linear time $O(n+m)$, where $n$ is the number of vertices and $m$ is the number of edges in the graph.

Explanation

Topological sorting is an ordering of the vertices in a directed acyclic graph (DAG) such that for every directed edge u→v vertex u comes before vertex v in the ordering. It is widely used in scenarios where you need to respect precedence relationships, such as task scheduling, course prerequisite ordering, and build systems.

Key Points:

• Directed Acyclic Graph (DAG): Topological sorting can only be performed on a directed acyclic graph, meaning it does not have any cycles.
• Ordering: The output of a topological sort is a linear sequence of vertices.

How It Works:

There are a couple of common methods to achieve a topological sort:

1. Kahn’s Algorithm (Using In-Degree):
   • Compute the in-degree (number of incoming edges) for each vertex.
   • Enqueue all vertices with an in-degree of 0.
   • While the queue is not empty:
     • Remove a vertex u from the queue and add it to the topological order.
     • For each neighbour v of u, reduce its in-degree by 1.
     • If v’s in-degree becomes 0, enqueue v.
   • If the graph has edges left after all nodes are processed, it means there is a cycle (not a DAG).
2. Depth-First Search (DFS)-Based Approach:
   • Perform a DFS traversal on the graph.
   • During the traversal, when visiting a vertex, mark it as visited.
   • Once all its neighbors are fully visited, add it to a stack.
   • At the end of the traversal, the vertices in the stack represent the topological order in reverse; simply pop elements from the stack to get the correct order.

Example: Leetcode Course Schedule II