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?