Algorithme pour trouver le nombre total d'ensembles connectés dans une matrice

Je ne pense pas que vous aurez besoin de penser comme un graphique général problème et d'appliquer l'algorithme comme BFS ou DFS.

Vous aurez besoin de faire trois analyses de la matrice.

analyse 1:

commencer par le haut

1. donner à chaque nombre de 1 à 1..n, en vous exemple de la première ligne après cette étape pourrait ressembler
   

   1 0 0 2

2. aller à la ligne suivante et pour chaque 1 de la rangée de vérifier si le voisin de gauche est non-0
   • si non 0 prendre la valeur à gauche
   • vérifier si 0 non 0 voisins dans la ligne précédente et de prendre sur la valeur de la plus à gauche d'un
   • si toutes les personnes sont égales à 0 que simplement ajouter 1 au nombre maximal donné jusqu'à présent
3. répéter 2 jusqu'à ce que la dernière ligne a été traitée

et par votre exemple, devrait se présenter comme suit

1 0 0 2
0 0 2 0
0 0 2 0
3 0 0 2

scan 2:

commencer par le bas
vérifier si chaque voisin a le même numéro que la gauche plus voisin ainsi que le même nombre que le prochain dans la ligne ci-dessous il

en gros si vous avez une matrice comme ce

1 0 2

1 0 2

0 1 0

pour vérifier s'assurer qu'un ensemble a vraiment le même nombre

analyse 3:

compter le nombre de non-0 entrées dans la matrice

Vous souhaitez utiliser un disjoints ensemble discbased et de l'algorithme. Cela permettra de choisir un représentant unique pour chaque composante connexe, qui vous pouvez compter à la fin.

À évaluer efficacement les éléments qui sont voisins, vous pouvez numériser la matrice ligne par ligne, le maintien d'une liste de segments consécutifs de 1') de la ligne précédente, en déterminant quels sont les segments sur la ligne courante sont adjacentes.

Pythonic mise en Œuvre, Plus compréhensible code:

# sea is 2 D array of 0 and 1s we have to find 1's group surrounded by 0's
def dfs(sea, i, j, b, h, visited):
    surround = ((-1, -1), (0, -1), (1, -1),
                (-1, 0), (1, 0),
                (-1, 1), (0, 1), (1, 1)
                )
    if can_visit(sea, i, j, b, h, visited):
        for s in surround:
            visited[(i, j)] = 1
            dfs(sea, i + s[0], j + s[1], b, h, visited)


def can_visit(sea, i, j, b, h, visited):
    if i >= 0 and j >= 0 and i < b and j < h:
        if (i, j) not in visited and sea[i][j] == 1:
            return True


def find_island(sea):
    visited = {}
    h = len(sea)
    count = 0
    for i, row in enumerate(sea):
        b = len(row)
        for j, item in enumerate(row):
            if can_visit(sea, i, j, b, h, visited):
                count += 1
                dfs(sea, i, j, b, h, visited)
    return count


sea = [[1, 1, 0, 0, 0],
       [0, 1, 0, 0, 1],
       [1, 0, 0, 1, 1],
       [0, 0, 0, 0, 0],
       [1, 0, 1, 0, 1]
       ]

print find_island(sea)

Si vous voulez le faire juste par votre matrice (sans mémoire), procédez comme suit:

Ensemble scanner position [0,0]

1. Définir un compteur à zéro.
2. Analyse de la matrice à partir d'un scanner en position rangée par rangée (et de la cellule par cellule) et de trouver un 1 et définir scanner position de l'élément suivant après cette 1si il n'est pas tout 1 passez à l'étape 6.
3. Jeu liées l'une à counter+2 et de manière récursive trouver l'ensemble de ses 1 voisins et aussi de mettre à count + 2.
4. count = count + 1
5. Passez à l'étape 2.
6. sortie count.

PS: Il est clair que si le scanner position est plus grande que la taille de la matrice de votre algorithme se termine (je n'ai pas écrit cela pour éviter la confusion).

Juste continuer à chercher dans l'Est, le Sud-est, au Sud et à direction de sud-ouest à une aller de manière récursive pour chaque nœud ayant la valeur 1.
Si l'appel à la visite de la fonction est un nouvel appel et pas de récursivité augmentation des composants raccordés.

import java.util.Scanner;

public class Solution {

    public static void visit(int[][] ar, boolean[][] v,int i, int j){
        int size = ar.length;
        if(ar[i][j] == 1){
            v[i][j] = true;
            if(j>0 && i<size-1){
                visit(ar,v,i+1,j-1); //SouthWest
            }
            if(i<size-1){
                visit(ar,v,i+1,j); //South
                if(j < size-1)
                    visit(ar,v,i+1,j+1); //SouthEast
            }
            if(j<size-1)
                visit(ar,v,i,j+1); //East
        }
    }

    public static void main(String[] args) {
        int[][] ar;
        int count = 0;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ar = new int[n][n];
        boolean[][] v = new boolean[n][n];
        for(int i=0; i<n ; i++) {
            for(int j=0; j<n; j++){
                ar[i][j] = sc.nextInt();
                v[i][j] = false;
            }
        }

        for(int i=0; i<n ; i++) {
            for(int j=0; j<n; j++){                
                if(ar[i][j] == 1 && !v[i][j]){
                    count++;
                    visit(ar,v,i,j);
                }
            }
        }
        System.out.println(count);
    }
}

Pour python essayer:

import numpy
from scipy import ndimage

data = [[0, 0, 1, 0, 0, 1, 0, 0],
        [1, 0, 0, 0, 0, 0, 0, 1],
        [0, 0, 1, 0, 0, 1, 0, 1],
        [0, 1, 0, 0, 0, 1, 0, 0],
        [1, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 1, 1, 0, 1, 1, 0],
        [1, 0, 1, 1, 0, 1, 1, 0],
        [0, 0, 0, 0, 0, 0, 0, 0]]

label, index = ndimage.label(data, numpy.ones((3, 3)))

print label, index

[[0 0 1 0 0 2 0 0]
 [3 0 0 0 0 0 0 4]
 [0 0 5 0 0 6 0 4]
 [0 5 0 0 0 6 0 0]
 [5 0 0 0 0 0 0 0]
 [0 0 7 7 0 8 8 0]
 [9 0 7 7 0 8 8 0]
 [0 0 0 0 0 0 0 0]] 9