8
$\begingroup$

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.

$\endgroup$
12
$\begingroup$

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 $1$ or $2$. Similarly the entries in $A^k$ tell you all pairs of nodes that are connected by a path of length $k$ or less. 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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the answer, I think I'll use that. What about the eigen vectors mention in the linked question? $\endgroup$ – Howcan Jul 11 '14 at 22:35
  • $\begingroup$ This works very nicely but it gets very slow very quickly. Any other ideas? $\endgroup$ – Howcan Jul 12 '14 at 21:56
  • 1
    $\begingroup$ @Howcan you can do "breadth first search" by initializing a hash table set with any one vertex, and then taking the neighbors of that vertex and hashing them and adding them to your hash table if they aren't already there, and then take the newly found vertices and hash all of their neighbors and add any newly found vertices, then repeat etc. After $n$ iterations you will either have all nodes in your set of hashed nodes found, or you won't which will tell you if the graph is connected. Complexity of this method is $O(n^2)$, vs. $O(n^3 \log n)$ for successive squaring of the adjacency matrix. $\endgroup$ – user2566092 Jul 13 '14 at 21:57
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.