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