How to check if a digraph is strongly connected with its adjacency matrix?

Question

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.

NeitherNor · Answer

I guess the problem boils down to the question if a vertex is always reachable from itself. Consider e.g. the graph $G=(V,E)$, with $V={a}$ and $E={}$. Trivially, the adjacency matrix of $G$ is $A=0$. The question if $G$ is strongly connected boils down to the question if you consider $a$ to be reachable from itself. If you answer this question with "no", you should use the formula $B=A^1+ldots+A^n=A=0$. If you answer this question with "yes", you should use the formula $B=I+A^1+ldots A^{n-1}=I=1$.

Both interpretations are useful, and which one you take depends on the specific interpretation of $G$.

Andrew Au · Answer

The quickest way to do so is

Convert this into an adjacency list (this take $ O(n^2) $) time, and then
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.

How to check if a digraph is strongly connected with its adjacency matrix?

2 Answers

Add your own answers!

Ask a Question