Topological Sorting (Topological Sorting)

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

Space Complexity Graph

Time-Space Tradeoff