Нахождение наибольшего связанного дерева в матрице

Question

Предположим, у меня есть матрица MxN, заполненная значениями от 0 до 5. Теперь я хочу определить самое большое связанное дерево в этой матрице, где значения матрицы считаются узлами.Пара узлов называется соединенной, если ее узлы расположены рядом друг с другом либо по горизонтали, либо по вертикали, и если значение обоих узлов одинаково.Размер дерева равен узлам в дереве.

Пример:

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

На левой стороне 1-узлы на левой стороне образуют наибольшее дерево.На правой стороне 3-узлы образуют самое большое дерево, в то время как есть два других дерева, состоящих из 2-х узлов.

Я знаю, что мог бы выполнить простой поиск в глубину, но мне интересноесли есть что-то общеизвестное, что я упускаю, может быть, в области теории графов (например, алгоритм минимального связующего дерева Крускала, но для этого примера).

Answer 1

Вы ищете непересекающиеся множества, поэтому я бы предложил структуру данных по непересекающимся наборам и алгоритм поиска / объединения:

см. http://en.wikipedia.org/wiki/Disjoint-set_data_structure#Disjoint-set_forests

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

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

Сложность вычислений будет O (MN A ^-1 (MN, MN)), где A ^-1 - обратное значениеФункция Аккермана, которую можно считать небольшой константой (<5) для любого полезного значения MN.И дополнительная сложность хранения будет O (MN). </p>

Answer 2

Эффективно то, что вы ищете, это подключенные компоненты. Подключенный компонент - это набор узлов, куда вы можете перейти от любого узла к любому другому в пределах этого компонента .

Связанные компоненты применимы, как правило, к графику. Связанные компоненты могут быть найдены с помощью BFS/DFS, и с точки зрения сложности алгоритма с учетом входных данных матрицы смежности лучшего способа сделать это не существует. Время выполнения алгоритма составляет O(N^2), где N - количество узлов в графе.

В вашем случае граф имеет больше ограничений, например, каждый узел может быть смежным не более чем с 4 другими узлами. С BFS/DFS это дает вам время работы O(4N) = O(N), где N - количество узлов. Не может быть алгоритма с лучшей сложностью, так как вам нужно рассмотреть каждый узел хотя бы один раз в худшем случае.