Find 'Connected Components' in undirected, unweighted graph coded as a 2d array

Question

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?

• Hey: 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.
• Michael: Thanks, I did't know about flood fill. I'll check it out.

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

• J Trana: 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.