поиск в глубину с помощью 2D Array

Question

У меня есть такой массив:

0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0 0 0 0
0 1 1 1 1 0 0 1 0 1 0
0 1 1 0 1 0 0 0 0 1 1
0 0 0 1 1 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 0 0

И я хочу сгруппировать элементы, которые равны '1'.

Итак, вы видите, у меня есть классические DFS с использованием стека. Вопрос в том, если у меня есть матрица, подобная приведенной выше, какова временная сложность этого алгоритма, где n - это количество элементов матрицы. (Строка *, столбец). Если это хуже, чем O(N) (поскольку я должен пройти через весь двумерный массив), какой подход поможет мне улучшить этот алгоритм?

Answer 1

Пример алгоритма O (n * log n)

(где n - количество элементов матрицы)

Идея алгоритма заключается в следующем.

1. Инициализировать набор деревьев необработанных элементов U , добавив в него все матричные элементы
2. Пока U еще не пусто, возьмите любой u из U и проверьте его значение
   • Если u = '0', просто удалите его, то есть U : = U \ {u}
   • Если u = '1', то начать исследование DFS (u, U)

Где процедура DFS (u, U) использует матрицу для исследования соседей '1' u .

Однако здесь идет кикер, DFS (u, U) также удаляет каждый обнаруженный элемент из U .

Довольно легко понять и доказать, что этот алгоритм действительно всегда заканчивается в O (n * log n). Удаление элемента из набора деревьев имеет сложность O в худшем случае (log n). Каждый прогон DFS (u, U) может посещать не более | U | элементов, и каждый элемент, посещаемый любым способом, удаляется из U по мере выполнения , Алгоритм завершается, когда U становится пустым.

Краткое резюме

Можно создать алгоритм O (n ^ 2) , например, запустив DFS для каждого элемента независимо от ваших ранее полученных знаний. Использование любого механизма, гарантирующего, что вы не запускаете DFS на уже обнаруженной группе / острове, может привести к превосходному алгоритму.

Извините, что я не могу проанализировать ваш собственный алгоритм напрямую, но это может помочь вам сделать это самостоятельно.

Answer 2

Нижняя граница алгоритма, который вам нужно разработать, должна быть O(m+n) - я рассматриваю количество строк и столбцов как m и n соответственно.Это потому, что вам все равно нужно пройти весь 2D-массив.Если вы решаете эту проблему, используя два цикла for, это также займет O(m+n).Для каждого элемента в вашей матрице вы будете сравнивать с другими 4 смежными элементами и, следовательно, общий размер проверки будет <= 4mn.

Я думаю, что нет лучшего способа решить эту проблему менее чем за O(m+n) время.

Обратите внимание, что в вашем вопросе, если вы рассматриваете m+n = N, то сложность, на которую я ссылаюсь, равна O(N).