Given an undirected, unweighted graph coded as a 2d array, how can I find the number of different connected components?ExampleThere is the following 2d array (I'm not putting any brackets to make it more readable):1 1 3 11 2 2 21 3 3 24 4 1 4Since 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 problemA 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 11 0 0 01 0 0 0 0 0 1 0 For number 2:0 0 0 00 2 2 20 0 0 20 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?
Find 'Connected Components' in undirected, unweighted graph coded as a 2d array
algorithms;graph