Dato un grafico non orientato, non ponderato, codificato come array 2d, come posso trovare il numero di diversi componenti connessi?
Esempio
C'è il seguente array 2d (non sto mettendo alcuna parentesi per renderlo più leggibile):
1 1 3 1
1 2 2 2
1 3 3 2
4 4 1 4
Poiché ciascun numero discreto può creare un componente con lo stesso numero / colore (non è possibile raggruppare insieme un numero diverso adiacente). Questo dovrebbe restituire 8.
I miei pensieri sul problema
Una possibile soluzione al problema sarebbe considerare ogni diverso numero come una versione del problema definita e risolta qui .
Ad esempio, per il numero 1:
1 1 0 1
1 0 0 0
1 0 0 0
0 0 1 0
Per il numero 2:
0 0 0 0
0 2 2 2
0 0 0 2
0 0 0 0
ecc.
Tuttavia, la mia considerazione con questo approccio è che probabilmente richiederebbe iterating | colors | volte attraverso l'array originale o allocando | colors | array.
Un altro approccio sarebbe quello di associare ciascun colore con le sue coordinate nel grafico, in questo modo:
1: <00, 01, 03, 10, 20, 32>
2: <11, 12, 13, 23>
3: <02, 21, 22>
4: <30, 31, 33>
Tuttavia questo approccio richiede di controllare tutte le combinazioni di coordinate per l'adiacenza.
I tuoi pensieri?