IsStronglyConnected('G') returns true if the input graph G is a strongly connected graph and returns false otherwise.

StronglyConnectedComponents(G) command computes the maximal subgraphs of G which are strongly connected.  It returns them as a list of lists of vertices where the number of lists indicates the number of strongly connected components.

By default the result is sorted by size of the subgraph. The optional parameter sorted=false can be used to preserve the order as computed by the algorithm.

A graph G is strongly connected if for each vertex u in G there is a path to every other vertex in G. Note that a graph with fewer than two vertice is trivially strongly connected.

If G is an undirected graph, then being strongly connected is equivalent to being connected.

An example of a strongly connected graph is the directed cycle graph.

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$T≔\mathrm{Digraph}\left(\left[1\,2\,3\right]\,\left\{\left[1\,2\right]\,\left[1\,3\right]\,\left[2\,3\right]\,\left[3\,2\right]\right\}\right)$

$T≔\mathrm{Graph\; 1:\; a\; directed\; graph\; with\; 3\; vertices\; and\; 4\; arc(s)}$

$\mathrm{DrawGraph}\left(T\right)$

$\mathrm{IsConnected}\left(T\right)$

$\mathrm{true}$

$\mathrm{IsStronglyConnected}\left(T\right)$

$\mathrm{false}$

$\mathrm{ConnectedComponents}\left(T\right)$

$\left[\left[1\,2\,3\right]\right]$

$\mathrm{StronglyConnectedComponents}\left(T\right)$

$\left[\left[1\right]\,\left[2\,3\right]\right]$

$\mathrm{IsStronglyConnected}\left(\mathrm{Digraph}\left(\mathrm{Trail}\left(1\,2\,3\,4\,5\right)\right)\right)$

$\mathrm{false}$

$\mathrm{IsStronglyConnected}\left(\mathrm{Digraph}\left(\mathrm{Trail}\left(1\,2\,3\,4\,5\,1\right)\right)\right)$

$\mathrm{true}$

$G≔\mathrm{Digraph}\left(\left\{\left[1\,2\right]\,\left[2\,3\right]\,\left[3\,4\right]\right\}\right)$

$G≔\mathrm{Graph\; 2:\; a\; directed\; graph\; with\; 4\; vertices\; and\; 3\; arc(s)}$

$\mathrm{StronglyConnectedComponents}\left(G\right)$

$\left[\left[4\right]\,\left[3\right]\,\left[2\right]\,\left[1\right]\right]$

$\mathrm{AddArc}\left(G\,\left[4\,3\right]\right)$

$\mathrm{Graph\; 2:\; a\; directed\; graph\; with\; 4\; vertices\; and\; 4\; arc(s)}$

$\mathrm{StronglyConnectedComponents}\left(G\right)$

$\left[\left[2\right]\,\left[1\right]\,\left[3\,4\right]\right]$

$\mathrm{DrawGraph}\left(G\right)$

$\mathrm{AddArc}\left(G\,\left[4\,2\right]\right)$

$\mathrm{Graph\; 2:\; a\; directed\; graph\; with\; 4\; vertices\; and\; 5\; arc(s)}$

$\mathrm{StronglyConnectedComponents}\left(G\right)$

$\left[\left[1\right]\,\left[2\,3\,4\right]\right]$