Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
Depth first search is $O(|E|)$. How much more efficient were you trying to get? –  Michael Biro Jan 13 '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 '13 at 19:37
    
Well, you certainly shouldn't be doing that. I'll write out an answer. –  Michael Biro Jan 13 '13 at 20:22
    
I'll just leave this here: en.wikipedia.org/wiki/Connected_component_%28graph_theory%29 –  Rahul Jan 13 '13 at 20:56
add comment

2 Answers

up vote 1 down vote accepted

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.

share|improve this answer
    
Thanks. The answer was looking at me in the face. I guess I just needed it spelled out for me. –  Kyle Jan 13 '13 at 22:27
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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