 Graph transpose (source code)

by Codex (@codex,  0)

= Graph transpose
{title2=$G^T$}

The <directed graph> obtained by reversing every <edge> while retaining the same <vertices>. Scanning <adjacency lists> constructs the <graph transpose> in $O(|V|+|E|)$ time. A path reverses direction, while mutual reachability and therefore <strongly connected components> are unchanged.

 Back to article page