graphs/others/topological-sort

Topological sort algorithm of a directed acyclic graph.

Time complexity: O(|E| + |V|) where E is a number of edges and |V| is the number of nodes.

Source:

graphs/others/topological-sort.js, line 23

Parameters:

Name	Type	Description
`graph`	`Array`	Adjacency list, which represents the graph.

Returns:

Type:: Array

Ordered vertices.

Example

var topsort =
 require('path-to-algorithms/src/graphs/' +
'others/topological-sort').topologicalSort;
var graph = {
    v1: ['v2', 'v5'],
    v2: [],
    v3: ['v1', 'v2', 'v4', 'v5'],
    v4: [],
    v5: []
};
var vertices = topsort(graph); // ['v3', 'v4', 'v1', 'v5', 'v2']