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.