Function graph_algorithms::list_of_algorithms::kosaraju::kosaraju::kosaraju_algorithm

pub fn kosaraju_algorithm(adj_list: &Vec<Vec<usize>>) -> Vec<Vec<usize>>

The Kosaraju’s algorithm is used to find strongly connected components. Given a directed graph represented as an adjacency list (Vec[Vec[]]), returns a vector of strongly connected components.

Arguments

• adj_list - A directed graph represented as an adjacency list. Each vector in the adjacency list represents the vertices that the corresponding vertex has an outgoing edge to.

Returns

• list_of_scc - A list of strongly connected components which are internally in sorted order represented as Vec[Vec[]].

Example

use kosaraju::kosaraju_algorithm;

let adj_list = vec![
    vec![1],       // Node 0 has edge to node 1
    vec![2],       // Node 1 has edge to node 2
    vec![0, 3],    // Node 2 has edges to nodes 0 and 3
    vec![4],       // Node 3 has edge to node 4
    vec![5],       // Node 4 has edge to node 5
    vec![3],       // Node 5 has edge to node 3
];

kosaraju_algorithm(&adj_list);