[Math] How to check if a digraph is strongly connected with its adjacency matrix

graph theory

Given a digraph G and its adjacency matrix A, which is the easiest way to check if it is strongly connected?

In the case of an undirected graph I should check that the matrix $ A+A^2+A^3+…+A^{n-1}$ has only nonzero elements with n the number of vertices of the graph. Is the same for a directed graph?

Lipschutz says the matrix B I should check for the case of a directed graph is $ B = A+A^2+…+A^n $ with n the number of vertices (Discrete Mathematics). So should I add one more power of the matrix for the case of a digraph?. Is that additional term really needed?

In other sources It seems that the matrix to check is $ B = I+A+A^2+…+A^{n-1} $.

I would appreciate any help with this doubts.

Best Answer

The quickest way to do so is

  1. Convert this into an adjacency list (this take $ O(n^2) $) time, and then
  2. Run Tarjan's algorithm, this take $ O(m + n) $ time.

Overall running time should be $ O(n^2) $

As usual $ n $ stands for the number of nodes and $ m $ stands for the number of edges. Any matrix identity above is slow compare to this.

Arguably this is the fastest possible asymptotically as one must read the input completely anyway, and that itself takes $ O(n^2) $ time.

Related Question