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

-

1
Depth first search is $O(|E|)$. How much more efficient were you trying to get? – Michael Biro Jan 13 at 18:59
Very valid question. In my particular case, I'm writing a program, and my current algorithm needs to make a copy of the grid to do its current depth first search because it deletes the node from the grid when it runs. Furthermore, I intend to evaluate the distinct groups further such as if a group breaks up should a node be deleted. My thought was that if I already had an adjacency matrix and a quick way to evaluate a graph using it, then I could just persist the matrix rather than making copy after copy. – Kyle Jan 13 at 19:37
Well, you certainly shouldn't be doing that. I'll write out an answer. – Michael Biro Jan 13 at 20:22
– Rahul Narain Jan 13 at 20:56

## 2 Answers

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.

-

Thanks. The answer was looking at me in the face. I guess I just needed it spelled out for me. – Kyle Jan 13 at 22:27

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

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 42, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9620102047920227, "perplexity_flag": "head"}