Checking connectivity of adjacency matrix

Solution 1:

If you put all 1 on the diagonal of your adjacency matrix $A$, and all edge weights are positive then when you multiply $A^2 = A*A$ you get a non-zero entry $a_{ij}$ in $A^2$ if and only if there exist non-zero $a_{ik}$ and $a_{kj}$ in $A$ for some $k$, i.e. there is a path of length $2$ between $i$ and $j$ if $k\neq j$ and $k\neq i$ and there is a path of length $1$ if $k = j$ or $k = i$. So the non-zero entries in $A^2$ tell you all pairs of nodes that are connected by a path of length $2$. Similarly the entries in $A^k$ tell you all pairs of nodes that are connected by a path of length $k$. So if you start with $A$ and keep squaring until you get $A^k$ where $k \geq n$ where $n$ is the number of nodes, then the non-zero entries in row $i$ tell you all the nodes that are connected to node $i$ (since two connected nodes must be connected by a path of length $n$ or less). So if you have a row in $A^k$ that is all non-zero, then the graph is connected. If the graph is not connected, you can similarly tell the connected components from the rows of $A^k$.

Solution 2:

I know that the question is old and that the first response is correct. However, due to its importance, I would like to point to a more efficient and more elegant alternative. Using the Fiedler value, i.e. the second smallest eigenvalue of the Laplacian matrix of G (i.e. $L=D-A$) we can efficiently find out if the graph in question is connected or not, in an algebraic way. In other words, "The algebraic connectivity of a graph G is greater than 0 if and only if G is a connected graph" (from the same Wikipedia article). If this eigenvalue is positive, then the graph is connected. The other efficient (algorithmic) alternative is to run the connected components algorithm (recursively running Depth-First-Search) we can find all connected components and see if the biggest/first one includes all nodes of the graph.