Easiest way to determine all disconnected sets from a graph? Suppose that I have a un-directed graph of nodes and edges, I would like to know all sets of nodes that do not connect with any other nodes in the graph.
Here is a concrete example to help you picture what I'm asking. In the following graph, all x nodes are connected to their adjacent (diagonal included) x nodes and the same goes for o nodes and b nodes.
x o o
b x o
b b x  
I wrote an algorithm that does this by taking a node and using depth first search to find all nodes connected to it. Then I remove those nodes from the graph and repeat with a new node until there are no more nodes left in the graph.
I'm starting to think that this isn't the most efficient method and that there has to be a way to do this using an adjacency matrix or something similar. If I were to translate the above graph into an adjacency matrix and name each node (1..9, left to right, top to bottom), it would look like this:
~~ 1 2 3 4 5 6 7 8 9
1 | 0 0 0 0 1 0 0 0 0
2 | 0 0 1 0 0 1 0 0 0
3 | 0 1 0 0 0 1 0 0 0
4 | 0 0 0 0 0 0 1 1 0
5 | 1 0 0 0 0 0 0 0 1
6 | 0 1 1 0 0 0 0 0 0
7 | 0 0 0 1 0 0 0 1 0
8 | 0 0 0 1 0 0 1 0 0
9 | 0 0 0 0 1 0 0 0 0  
I put zeros down the diagonal, but I'm not sure if that's right notation for an adjacency matrix. Also, since it's an undirected graph, I know that the matrix is symmetrical down the diagonal. Beyond that, I'm stuck. I just have a feeling that something about this matrix will make it easier to identify the 3 distinct unconnected groups beyond what I've done already. Does anyone have an idea for an algorithm that will help me?
Thanks in advance.
 A: Say you have an adjacency matrix like the one in your question. You can determine connected components by doing a breadth-first (or depth-first) search in the matrix without having to remake copies or delete vertices.
You'll start each connected component search with the first vertex that you haven't placed in a component yet. The first one will be vertex $v_1$:
Initialize the connected component $C_1 = \{v_1\}$ and then move across $v_1$'s row in the adjacency matrix. We see that $v_1$ is adjacent to $v_5$, so $v_5$ gets added to the component $C_1 = \{v_1,v_5\}$, and we move on to $v_5$'s row. $v_5$ is connected to $v_1$ (seen already) and $v_9$, so add $v_9$ to $C_1$, and move on to $v_9$, which is adjacent to $v_5$ (seen already). Since we've reached the end of this tree, we're done with this component and get $C_1 = \{v_1,v_5,v_9\}$.
Now, take the next vertex that we haven't seen yet ($v_2$) and set $C_2 = \{v_2\}$. $v_2$ is adjacent to $v_3$ and $v_6$, so we get $C_2 = \{v_2,v_3,v_6\}$, and the next vertex to check is $v_3$, which is adjacent to $v_2$ and $v_6$, both seen. Then move to the next vertex $v_6$ and note that its adjacent to $v_2$ and $v_3$ (both seen), so we're done with this component too.
On to $C_3$, the same procedure gets us $C_3 = \{v_4,v_7,v_8\}$. All vertices $v_1$ through $v_9$ have been seen at this point so we're done, and the graph has $3$ components.
A: Here is a fancy way of doing it. Construct the Laplacian matrix $L = D - A$ and find the eigenvalues and eigenvector of $L.$ The eigenvalues are $\lambda = \{0,0,0,1,3,3,3,3,3\}$ in your case and the first three zeros tell me that there are 3 disconnected sets. The associated eigenvectors are
$$
\begin{eqnarray}
 \mathbf{x}_1 &=& \left[\frac{-1}{\sqrt{3}}, 0,0,0, \frac{-1}{\sqrt{3}}, 0,0,0, \frac{-1}{\sqrt{3}}\right]^T,\\
\mathbf{x}_2 &=& \left[0,0,0,\frac{1}{\sqrt{3}},0,0,\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}},0\right]^T,\\
\mathbf{x}_3 &=& \left[0,\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}},0,0,\frac{1}{\sqrt{3}},0,0,0\right]^T.
\end{eqnarray}
$$
From indices of the nonzero entries I see the clusters are $C_1 = \{v_1, v_5, v_9\},$
$C_2 = \{v_4, v_7, v_8\},$ and $C_3 = \{v_2, v_3, v_6\}.$
A: [First, let me state that I do not know what algorithms people use to deal with this problem.]
The typical Adjacency matrix has 0's along the diagonal, representing that there is no self-loop. However, if you put 1's along the diagonal (i.e. add in self-loops for all vertices), then you will still have a real symmetric matrix that is diagnoalizable.
Recall that that the entires of matrix $A^n$ will give you the number of paths of length exactly $n$, from vertex $v_i$ to vertex $v_j$. So, we can take the matrix $A$ and raise it up to power $|V|$, and the connected components of the graph will appear as blocks, which anything that is not connected will have a 0. Note that adding of the 1 is necessary, to extend any path to obtain a path of length exactly $|V|$.

Not so sure: There could be variants around this, like calculating $(I-A)^{-1}$ which could be quicker, but not fail proof.
