Topological Sorting

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

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 2 of 2 algorithms

				See more
Tarjan's DFS based algorithm	1976	$O(V+E)$	$O(V)$
Kahn's algorithm	1962	$O(V+E)$	$O(V)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms