Алгоритм нахождения общего числа связанных множеств в матрице

я хотел знать, какой алгоритм я должен применить здесь. Был быДФС делать?

С учетом матрицы 2 d. Найти общее количество связанных наборов в этой матрице.

Связанный набор может быть определен как группа ячеек, в которой есть 1 упомянутая ячейка, и в которой есть хотя бы одна другая ячейка в том наборе, с которым они разделяют отношения соседей. Ячейка с 1 в нем и без соседа, имеющего 1 в нем, может рассматриваться как набор с одной ячейкой в нем. Соседи могут быть определены как все ячейки, смежные с данной ячейкой в 8 возможных направлениях (то есть N, W, E, S, NE, NW, SE, направление SW). Клетка не является соседом сама по себе.

Например:

1 0 0 1

0 0 1 0

0 0 1 0

1 0 0 1

количество подключенных наборов 3

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

Количество подключенных комплектов - 9.

Ответы на вопрос(11)

Маркировка подключенных компонентов Алгоритм предназначен для выделения связанных групп элементов (как для 4-связности, так и для 8-связности)

 18 июн. 2015 г., 17:55
Я нашел это легко читать и реализовать по сравнению с другими ответами. Спасибо!

Реализация Pythonic, более понятный код:

# 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)
 21 мая 2017 г., 21:09
Я думаю, что это лучший ответ здесь!

Для Python попробуйте:

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

У меня есть класс, чтобы помочь вам найти общее количество подключенных компонентов в вашем 2D-массиве. Мой класс не только дает вам общее количество, но также дает вам кластеры и визуализировать их для вас. Вы можете закомментировать те части, которые вам не нужны. Пожалуйста, смотрите этот класс в (Java):https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/ConnectedComponetns.java

Это не так сложно, как кажется. На самом деле, это очень сильно похоже на то, что профессор назначил бы для назначения на первом курсе информатики. Так что, если это домашняя работа, вы должны пометить ее как таковую.

Однако решение довольно простое.

for (int y = 0; y < arr.height(); y++)
{
   for (int x = 0; x < arr.width(); x++)
   {
      if (arr[x][y] == 1)
      {
         if (CheckIfConnected(x, y, arr))
         {
            connectedPositionsX.Add(x);
            connectedPositionsY.Add(y);
         }
      }
   }
}

Где connectedPositions будет связанным списком или тем, с чем вы хотите хранить наборы.

arr 2D-массив, содержащий матрицу указанного вами типа.

CheckIfConnected также может быть реализован довольно просто.

bool CheckIfConnected(int x, int y, int[][]arr)
    {
       if (arr.width() >= 2) || (arr.height() >= 2)
       {
          if ((x < arr.width()) && (x >= 0) && (y < arr.height()) && (y >= 0))
          {
            if ((x-1) >= 0) //West
            {
                if (arr[x-1][y] == 1)
                {
                    adjCount[x-1][y] += 1;
                    return true;
                }
            }
            if (((x-1) >= 0) && ((y-1) >= 0)) //Northwest
            {
                if (arr[x-1][y-1] == 1)
                {
                    adjCount[x-1][y-1] += 1;
                    return true;
                }
            }
            if ((y-1) >= 0) //North
            {
                if (arr[x][y-1] == 1)
                {
                    adjCount[x][y-1] += 1;
                    return true;
                }
            }
            if (((x+1) < arr.width()) && ((y-1) >= 0)) //Northeast
            {
                if (arr[x+1][y-1] == 1)
                {
                    adjCount[x+1][y-1] += 1;
                    return true;
                }
            }
            if ((x+1) < arr.width()) //East
            {
                if (arr[x+1][y] == 1)
                {
                    adjCount[x+1][y] += 1;
                    return true;
                }
            }

            //I'll let you implement Southeast to Southwest on your own,
            //the pattern is clear now.
          }
       }
       return false;
    }

Оттуда вы знаете, сколько раз вы находили пары в каждой позиции в сетке. Это поможет вам отслеживать ваши связи.

Счет в двумерном массивеadjCount отслеживает это для вас.

Вы также можете пройти и изменить алгоритм Дейкстры, чтобы сделать это рекурсивно для вас. Поскольку вы упомянули DFS (Поиск в глубину), я предполагаю, что ваш профессор или преподаватель хочет, чтобы вы решили это таким образом.

В таком случае:

Вот алгоритм Дейкстры в псевдокоде: http://en.wikipedia.org/wiki/Dijkstra& APOS; s_algorithm

Надеюсь, это поможет! Ура!

юго-восточном, южном и юго-западном направлениях за один проход рекурсивно для каждого узла, имеющего значение 1. Если функция вызова для посещения является новым вызовом, а не из рекурсии, увеличьте количество подключенных компонентов.

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);
    }
}

Я не думаю, что вам нужно будет рассматривать это как общую проблему с графом и применять любой алгоритм, такой какBFS или жеДФС.

Вам нужно будет сделать три сканирования матрицы.

scan 1:

начать с вершины

give every number each 1 with 1..n, in you example the first row would after that step would look like

1 0 0 2

go to the next line and for every 1 in the row check if the neighbor to your left is non-0 if non-0 take on the value to the left if 0 check for non-0 neighbors in the previous line and take on the value of the left most one if all of those are 0 that simply add 1 to the maximum number given so far repeat 2 until last line has been processed

и ваш пример должен выглядеть следующим образом

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

scan 2:

начинать снизу проверьте, есть ли у каждого соседа тот же номер, что и у самого левого соседа, а также тот же номер, что у соседа в строке ниже

в основном, если у вас есть такая матрица

1 0 2

1 0 2

0 1 0

чтобы убедиться, что набор имеет действительно один и тот же номер

scan 3:

подсчитать количество уникальных ненулевых записей в матрице

 15 янв. 2014 г., 16:39
Может кто-нибудь, пожалуйста, объясните второй шаг сканирования 1

вызовите рекурсивную функцию, которая помечает связанный компонент, если он еще не идентифицирован как находящийся в одном. Используйте рекурсию, чтобы найти подключенные компоненты. Проведите быстрый поиск где-нибудь, который скажет вам, был ли данный узел уже идентифицирован как находящийся в подключенном компоненте, чтобы избежать идентификации подключенных компонентов 2x и избежать бесконечных циклов при обходе подключенного компонента.

непересекающиеся множества структура данных и алгоритм. Это выберет уникального представителя для каждого подключенного компонента, который вы можете посчитать в конце.

Чтобы эффективно оценить, какие элементы являются соседями, вы можете сканировать матрицу построчно, сохраняя список сегментов (последовательных1's) из предыдущей строки, при этом определяя, какие сегменты в текущей строке смежны с ними.

 29 июн. 2012 г., 00:48
Я знаю, что такое непересекающиеся множества, один из наиболее важных методов в непересекающихся множествахFind метод (см. вики), на самом деле я спросил вас, как вы будете реализовыватьFind метод? (По этой постановке задачи.).
 29 июн. 2012 г., 01:01
Корень дерева является представительным элементом. Ссылка на википедию описывает это, а также оптимизации, необходимые для достижения амортизированной производительности O (inverseAckermann (N)).
 29 июн. 2012 г., 00:43
Краткое описание классических операций непересекающегося множества: каждое непересекающееся множество представлено в виде перевернутого дерева сparent только ссылки. Чтобы найти репрезентативный элемент набора, следуйтеparent ссылки, чтобы найти корень дерева. Чтобы объединить два дерева, найдите корень каждого и сделайте одно родительским для другого.
 29 июн. 2012 г., 00:09
Я не могу видеть, как вы будете назначать репрезентативный элемент для определенного набора, так что все другие элементы в наборе будут потомками этого элемента.

которые являются соседями друг друга, рассматриваются как один отдельный набор. Все 1 наa[1,4], a[2,3], a[3,3] а такжеa[4,4] сформируйте один набор и один вa[1,1] сформируйте один набор и один вa[4,1] образует один набор.

памяти), сделайте это следующим образом:

Установите положение сканера как [0,0]

Set a counter to zero. Scan matrix from current scanner position row by row (and cell by cell) and find one 1 and set scanner position to next element after this 1, if there isn't any 1 go to step 6. Set related one to counter+2 and recursively find all of its 1 neighbors and also set them to count + 2. count = count + 1 Go to step 2. output count.

PS: ясно, если позиция сканера больше, чем размер матрицы, ваш алгоритм будет завершен (я не писал этого, чтобы избежать путаницы).

Ваш ответ на вопрос