Next: Hashing, Previous: Sorting, Up: Sorting and Searching [Contents][Index]
(require 'topological-sort) or
The algorithm is inspired by Cormen, Leiserson and Rivest (1990) Introduction to Algorithms, chapter 23.
is a list of sublists. The car of each sublist is a vertex. The cdr is the adjacency list of that vertex, i.e. a list of all vertices to which there exists an edge from the car vertex.
is one of
Sort the directed acyclic graph dag so that for every edge from vertex u to v, u will come before v in the resulting list of vertices.
Time complexity: O (|V| + |E|)
Example (from Cormen):
Prof. Bumstead topologically sorts his clothing when getting dressed. The first argument to
tsortdescribes which garments he needs to put on before others. (For example, Prof Bumstead needs to put on his shirt before he puts on his tie or his belt.)
tsortgives the correct order of dressing: