Topological Sorting (Topological Sorting)

From Algorithm Wiki
Revision as of 14:45, 15 February 2023 by Admin (talk | contribs)
Jump to navigation Jump to search

Description

Given a graph or network, find a topological sorting of the graph. A list in topological order has a special property. Simply expressed: proceeding from element to element along any path in the network, one passes through the list in one direction only. Stated another way, a list in topological order is such that no element appears in it until after all elements appearing on all paths leading to the particular element have been listed.

Parameters

V: number of vertices

E: number of edges

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Kahn's algorithm 1962 $O(V+E)$ $O(V)$ auxiliary Exact Deterministic Time
Tarjan's DFS based algorithm 1976 $O(V+E)$ $O(V)$ auxiliary? Exact Deterministic Time
Dekel; Nassimi & Sahni Parallel Implementation 1981 $O( log² V)$ $O(V^{2})$?? Exact Parallel Time

Time Complexity Graph

Error creating thumbnail: Unable to save thumbnail to destination

Space Complexity Graph

Error creating thumbnail: Unable to save thumbnail to destination

Time-Space Tradeoff

Error creating thumbnail: Unable to save thumbnail to destination