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

algorithm matrix

703 просмотра

2 ответа

Я ищу способ найти количество подключенных (соседних) элементов в матрице. Мне дан 2D-массив объектов, где у каждого объекта может быть установлен флаг. Если флаг установлен, мне нужно посчитать количество соседей, для которых установлен флаг. Для каждого соседа процесс повторяется.

Смотрите изображение для визуализации проблемы: визуализация

Я думаю, что это довольно распространенная проблема. Как его зовут, чтобы я мог провести собственное исследование?

Автор: Nils Schikora Источник Размещён: 12.11.2019 09:40

Ответы (2)


6 плюса

Решение

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

Возможный псевдокод может быть:

DFS(v,visited):
   if v is not set: 
       return []
   else:
        nodes = [v]
        for each neighbor u of v:
            if u is not in visited:
                  visited.add(u)
                  nodes.addAll(DFS(u,visited))
        return nodes

Если вы начнете с некоторой точки v, он вернет список, содержащий все узлы, связанные с ним v(включая vсебя), и вы можете легко установить их «значение» как size(nodes).

Следующий псевдокод помечает ВСЕ узлы размером их «кластера»:

markAll(V): //V is the set of all cells in the matrix
    visited = [] //a hash set is probably best here
    while (V is not empty):
       choose random v from V
       visited.add(v)
       nodes = DFS(v,visited)
       for each u in nodes:
            value(u) = size(nodes)
       V = V \ nodes //set substraction

Сложность такого подхода будет O(|V|) = O(n*m)- поэтому линейна по размеру матрицы (которая равна n * m)

Автор: amit Размещён: 21.04.2015 09:33

5 плюса

Как насчет использования структуры данных Disjoint set или union-find ?

В основном:

Всякий раз, когда добавляется флаг или вы замечаете, что элемент имеет флаг, сканируйте соседей этого элемента. Как только вы обнаружите в нем элемент с флагом, вы объедините элементы вместе, указав им один и тот же родительский элемент. Либо прямо, либо рекурсивно.

Ведите подсчет количества элементов для каждого кластера.

Автор: Christofer Ohlsson Размещён: 21.04.2015 09:34
Вопросы из категории :
32x32