graphs/others/tarjan-connected-components

Tarjan's algorithm for finding the connected components in a graph.

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

Source:

graphs/others/tarjan-connected-components.js, line 4

Parameters:

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

Returns:

Type:: Array

Connected components.

Example

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