／var／logmarcus chiu

Topological Sort／Ordering

Created on · Last Modified on

Topological Sort - Topological Ordering
  • is a linear ordering of a directed graph’s vertices such that for every directed edge 𝑢𝑣 from vertex 𝑢 to vertex 𝑣, 𝑢 comes before 𝑣 in the ordering

Examples

The graph shown to the left has many valid topological sorts, including:

  • 5, 7, 3, 11, 8, 2, 9, 10 (visual left-to-right, top-to-bottom)
  • 3, 5, 7, 8, 11, 2, 9, 10 (smallest-numbered available vertex first)
  • 5, 7, 3, 8, 11, 10, 9, 2 (fewest edges first)
  • 7, 5, 11, 3, 10, 8, 9, 2 (largest-numbered available vertex first)
  • 5, 7, 11, 2, 3, 8, 9, 10 (attempting top-to-bottom, left-to-right)
  • 3, 7, 8, 5, 11, 10, 2, 9 (arbitrary)