Topological Sort

A directed graph is a linear ordering of its vertices such that for every directed edge.

• Topological Tree
• Topological String
• Topological Sort
• Topological Short

Works by choosing vertices in the same order as the eventual topological sort.

• Khan’s Algorithm
• Depth-first Algorithm
• Parallel Algorithms
• Topological Sort Algorithm

An alternative algorithm for topological sorting is based on depth-first search.

• Parallel Algorithms
• Topological Sort Algorithm
• Khan’s Algorithm
• Depth-first Algorithm

A topological ordering can be constructed in time using a polynomial number of processors

• Depth-first Algorithm
• Parallel Algorithms
• Khan’s Algorithm
• Shortest Path Algorithm

The topological ordering can also be used to quickly compute.

• Uniqueness
• Hamiltonian Path
• Shortest Path Finding
• Shortcut Path Finding

The topological sort order is unique

• Unique Sort
• Hamiltonian Path
• Shortest Path Finding
• Uniqueness

Is a partial order in which, for every two objects x and y in the set, either x ≤ y or y ≤ x.

• Comparison sorting
• Partial order
• Total order
• Linear extension

Acronym of DAG

• Ditected acyclic graph
• Directed acyclic graph
• Directed acryclic graph
• Directed aciclic graph

depth-first-search-based algorithm is the one described by

• Tarjan (1976).
• Coffman–Graham (1975)
• Cormen et al. (2001)
• Dekel, Nassimi & Sahni (1981)

Used to quickly compute shortest paths through a weighted directed acyclic graph.

• Shortest path finding
• Adjacency matrix
• Uniqueness
• Topological ordering