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

Ответ 1

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

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

сканирование 1:

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

• дайте каждому числу каждый 1 с 1..n, в вашем примере первая строка будет после того, как этот шаг будет выглядеть так:

  1 0 0 2

• перейдите к следующей строке и для каждого 1 в строке проверьте, не соседствует ли сосед слева от 0
  • Если не-0 берет значение слева
  • если 0 проверить для не-0 соседей в предыдущей строке и взять значение самого левого
  • если все они равны 0, которые просто добавляют 1 к максимальному числу, указанному до сих пор
• повторить 2 до тех пор, пока последняя строка не будет обработана

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

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

сканирование 2:

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

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

1 0 2

1 0 2

0 1 0

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

сканирование 3:

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

Ответ 2

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

Ответ 3

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

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

Ответ 4

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

Ответ 5

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

# sea is 2 D array of 0 and 1s we have to find 1 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)

Ответ 6

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

Ответ 7

Если вы хотите сделать это только по вашей матрице (без дополнительной памяти), сделайте следующее:

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

• Установите счетчик на нуль.
• Сканировать матрицу из текущей позиции сканера по строке (и ячейке по ячейке) и найти один 1 и установить положение сканера на следующий элемент после этого 1, если нет 1 перейти к шагу 6.
• Задайте связанный с counter+2 и рекурсивно найдите всех его соседей 1, а также установите их в count + 2.
• count = count + 1
• Перейдите к шагу 2.
• output count.

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

Ответ 8

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

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

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

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

Счетчики в 2D-массиве adjCount отслеживают это для вас.

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

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

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

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

Ответ 9

Просто продолжайте поиск в восточном, юго-восточном, южном и юго-западном направлении за один раз рекурсивно для каждого node, имеющего значение как 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);
    }
}

Ответ 10

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

Ответ 11

Для 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