Easiest way to determine all disconnected sets from a graph?

Question

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.

Answer 1

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.

Answer 2

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