# Topological Sorting (Topological Sorting)

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)$ | Exact | Deterministic | Time |

Tarjan's DFS based algorithm | 1976 | $O(V+E)$ | $O(V)$? | Exact | Deterministic | Time |

Dekel; Nassimi & Sahni Parallel Implementation | 1981 | $O(\log^{2} V)$ | $O(V^{2})$?? | Exact | Parallel | Time |