Checking connectivity of adjacency matrix

Question

What do you think is the most efficient algorithm for checking whether a graph represented by an adjacency matrix is connected? In my case I'm also given the weights of each edge.

There is another question very similar to mine: How to test if a graph is fully connected and finding isolated graphs from an adjacency matrix

That answer seems to be good, except I don't really understand it. How does repeatedly squaring the matrix give information about its connectivity? There is another an answer that claims eigenvectors also give information about the connectivity of the graph, could anyone explain that as well?

I'm asking this because I don't have the background to understand the answers given, I'm just solving a problem that has to do with these topics. Searching around on google didn't give me an answer either, so hopefully someone can clear it up.

Answer 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$.

Answer 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.