0

Given an undirected, unweighted graph coded as a 2d array, how can I find the number of different connected components?

Example

There is the following 2d array (I'm not putting any brackets to make it more readable):

1 1 3 1
1 2 2 2
1 3 3 2
4 4 1 4

Since each discrete number can create a component with the same number/colour (different adjacent number cannot be clustered together). This should return 8.

My thoughts on the problem

A possible solution to the problem would be to consider each different number as a version of the problem defined and solved here.

For example, for number 1:

1 1 0 1
1 0 0 0
1 0 0 0 
0 0 1 0

For number 2:

0 0 0 0
0 2 2 2
0 0 0 2
0 0 0 0

etc.

However my consideration with this approach is that it would probably require either iterating |colours| times through the original array, or allocating |colours| arrays.

Another approach would be to associate each colour with a its coordinates in the graph, like this:

1: <00, 01, 03, 10, 20, 32>
2: <11, 12, 13, 23>
3: <02, 21, 22>
4: <30, 31, 33>

However this approach would require to check all combinations of coordinates for adjacency.

Your thoughts?

Improve this question
2
  • You could make a copy of the graph, then iterate through each node, doing a flood fill from that node. As you do the flood fill, change the value of each connected node to 0. At the end of the flood fill, increment a counter. When your iterator moves to the next node, skip it if it has a value of 0. At the end, each node should be 0 and your counter should contain the number of connected components.
    – Hey
    Nov 24, 2014 at 16:38
  • Thanks, I did't know about flood fill. I'll check it out.
    – Michael
    Nov 24, 2014 at 20:28

1 Answer 1

Reset to default
-1

Wikipedia has a nice little section on algorithms for this. @Hey's suggestion lines up with the recommendation for simply doing a bread- or depth-first search from the list of vertices.

Improve this answer
1
  • To my downvoter: could you please leave some constructive feedback? I answered this question in the interest of cleaning up old ones. As best I understand, there are classic answers to this variant of a classic problem. The most straightforward answer by Wikipedia states that the classic algorithm for this didn't appear to have a name and was common practice by 1973; therefore I didn't go into more specifics.
    – J Trana
    Jan 14, 2015 at 5:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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