Skip to main content

One doc tagged with "kahn's algorithm"

View All Tags

Topological Sort/Ordering

The goal of a topological sort is given a list of items with dependencies, (ie. item 5 must be completed before item 3, etc.) to produce an ordering of the items that satisfies the given constraints. In order for the problem to be solvable, there can not be a cyclic set of constraints. (We can't have that item 5 must be completed before item 3, item 3 must be completed before item 7, and item 7 must be completed before item 5, since that would be an impossible set of constraints to satisfy.) Meaning we can model this problem with a directed unweighted acyclic graph. When all the vertices are topologically ordered in a row all the edges go from left to right.