Algorithme efficace pour trouver les composants connectés

Fondamentalement, je ne vois aucune raison d'implémenter un algorithme compliqué puisque les voisins dans la grille sont très faciles à calculer comme

+----->
| [(0,0) - 0  ]   [(1,0) - 1st]   [(2,0) - 2nd]   [(3,0) - 3th]
| [(0,1) - 4th]   [(1,1) - 5th]   [(2,1) - 6th]   [(3,1) - 7th]
v [(0,2) - 8th]   [(1,2) - 9th]   [(2,2) -10th]   [(3,2) -11th]

// index for (2,1)
index_of_2_1 = (y * rows_count) + x = (1*4) + 2 = 6

Vous pouvez garder carrés dans quelque chose comme Listez > et accédez-y par index

Cependant, si vous voulez les conserver dans une simple List vous pouvez toujours le faire en calculant n index de l'élément n-ième comme

 +-------+-------+-------+
 |x-1,y+1|  x,y+1|x+1,y+1|
 +-------+-------+-------+
 |x-1,  y|  x,  y|x+1,  y|
 +-------+-------+-------+
 |x-1,y-1|  x,y-1|x+1,y-1|
 +-------+-------+-------+

Je suis d'accord avec les commentaires selon lesquels vous devez être précis dans votre question. Cependant, puisque vous avez demandé "certains carrés étant vérifiés deux fois", je peux répondre à cette partie. Vous pouvez gérer la matrice pour suivre les cellules déjà visitées. Au départ, toutes les cellules peuvent être définies sur 0. Une fois la cellule donnée traitée, vous pouvez la définir comme 1. Chaque fois que vous traitez une cellule, vérifiez simplement si elle est déjà visitée à l'aide de la matrice visitée.

Version courte

Je pense qu'un algorithme de recherche en profondeur d'abord pourrait vous aider.

Dans votre cas, chaque tuile peut être vue comme un nœud d'un graphe et une arête existe entre deux nœuds s'ils partagent un côté ou un coin.

Une belle vidéo expliquant le fonctionnement de cet algorithme que j'ai trouvé est ici: Depth First Recherche sur youtube

L'algorithme DFS est probablement très similaire à ce que vous avez tenté avec votre méthode récursive, la principale différence est cependant que vous «colorez» les nœuds / tuiles que vous visitez au fur et à mesure de votre progression l'algorithme. Plutôt que de conserver les nœuds explorés dans une structure de données séparée, je vous suggère d'en faire une propriété de chacune de vos tuiles.

Ensuite, si vous tombez sur une tuile que vous avez déjà visitée, vous ne l'explorez pas. Si vous avez exploré tous les voisins de votre nœud actuel, vous revenez au nœud que vous exploriez juste avant et explorez ses voisins (récursivement) jusqu'à ce que vous reveniez vers le nœud à partir duquel vous avez démarré l'algorithme.

Quelques détails supplémentaires liés à votre problème spécifique

Détection des voisins

Vous avez mentionné vos cases sont stockés dans une ArrayList. C'est bon. Mais cela ne vous empêche pas de construire un tableau 2D de carrés dont les cellules sont nulles s'il n'y a pas de carrés ou contiennent une référence à l'occurrence de carré située à cette position. À mon humble avis, cela rendrait la recherche de voisins beaucoup plus facile que de rechercher des collisions entre chaque paire de carrés (ce que je pense que c'est ce que vous faites actuellement).

Vous n'auriez pas à utiliser un tel tableau 2D pour quoi que ce soit d'autre dans votre programme. Je suis convaincu que cela rendrait les choses plus rapides pour un grand nombre de carrés.

Bien sûr, il existe d'autres structures de données qui faciliteraient la recherche d'intersections entre les nœuds d'un graphe. Par exemple, vous pouvez créer une matrice de contiguïté une fois et l'utiliser pour tout calcul ultérieur, mais vous n'ont pas à faire.

Exécution de DFS en utilisant votre exemple

Je vais utiliser une pile pour garder une trace de l'endroit où je suis dans les tuiles exploration. Je vais faire référence aux tyles par leurs coordonnées. La cellule à partir de laquelle nous démarrons l'algorithme est colorée en rouge sur votre figure et a des coordonnées (1,2).

L'algorithme est le suivant:

while (!stack.isEmpty()) {
  currentTyle = stack.top();
  boolean currentHasNeighborsToExplore = false;
  for (n in neighbors of currentTyle) {
    if (n is not explored) {
      n is explored;
      stack.add(n);
      currentHasNeighborsToExplore = true;
      break;
    }
  }
  if (!currentHasNeighborsToExplore) {
    stack.pop();
  }
}

Nous commençons l'algorithme avec votre tyle initial (1,2).

ÉTAPE 1

Pile: [(1,2)

Le haut de la pile est (1,2) p>

(1,2) a le voisin n: (2,2) qui est inexploré

(2,2) est maintenant exploré, nous l'ajoutons à la pile et passons à l'étape suivante

ÉTAPE 2

Pile: [(1,2) (2,2)

Le haut de la pile est (2, 2)

(2,2) a le voisin n: (1,2) qui est exploré

(2,2) a le voisin n: (3,1) qui est inexploré

(3,1) est maintenant exploré, nous l'ajoutons à la pile et passons à l'étape suivante

ÉTAPE 3

Pile: [(1,2) (2,2) (3,1)

Le haut de la pile est (3,1)

(3,1) a le voisin n : (2,2) qui est exploré

(3,1) a le voisin n: (4,2) qui est inexploré

(4,2) est maintenant exploré, nous ajoutez-le à la pile et passez à l'étape suivante

ÉTAPE 4

Pile: [(1,2) (2,2) (3,1 ) (4,2)

Le haut de la pile est (4,2)

(4,2) a le voisin n: (4,3) qui est inexploré p >

(4,3) est maintenant exploré, nous l'ajoutons à la pile et passons à l'étape suivante

ÉTAPE 5

Pile: [(1,2) (2,2) (3,1) (4,2) (4,3)

Haut de la pile est (4,3)

(4,3) a le voisin n: (4,2) qui est exploré

(4,3) n'a pas de voisins inexplorés, nous sortez-le de la pile et passez à l'étape suivante

ÉTAPE 6

Pile: [(1,2) (2,2) (3,1 ) (4,2)

Le haut de la pile est (2,2)

(4,2) a le voisin n: (4,3) qui est exploré p >

(4,2) a le voisin n: (5,1) qui est inexploré

(5,1) est maintenant exploré, nous l'ajoutons à la pile et passons à l'étape suivante p>

Étapes suivantes

À l'étape suivante, (5,1) n'a pas de voisins inexplorés, il sera sorti de la pile comme tous les styles suivants depuis il n'y a plus de voisins inexplorés.