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

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.