5
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Depth first search is $O(|E|)$. How much more efficient were you trying to get? $\endgroup$ Jan 13, 2013 at 18:59
  • $\begingroup$ 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. $\endgroup$
    – Kyle
    Jan 13, 2013 at 19:37
  • $\begingroup$ Well, you certainly shouldn't be doing that. I'll write out an answer. $\endgroup$ Jan 13, 2013 at 20:22
  • $\begingroup$ I'll just leave this here: en.wikipedia.org/wiki/Connected_component_%28graph_theory%29 $\endgroup$
    – user856
    Jan 13, 2013 at 20:56

3 Answers 3

5
$\begingroup$

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\}.$

$\endgroup$
1
  • $\begingroup$ This is actually a simple example of spectral clustering. $\endgroup$
    – JLT
    Jul 15, 2021 at 9:02
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks. The answer was looking at me in the face. I guess I just needed it spelled out for me. $\endgroup$
    – Kyle
    Jan 13, 2013 at 22:27
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .