algorithm - 在矩阵中寻找最大的连通树

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 节点组成。

我知道我可以做一个简单的深度优先搜索，但我想知道我是否遗漏了一些众所周知的东西，也许是在图论领域(比如 Kruskal 的最小生成树算法，但是对于这个例子)。

Answer 1

您正在寻找不相交的集合，所以我建议使用不相交的集合数据结构和查找/联合算法:

参见 http://en.wikipedia.org/wiki/Disjoint-set_data_structure#Disjoint-set_forests

并集运算是对称的，因此您实际上只需要将矩阵的每个元素与其右边的邻居和下面的邻居进行比较，当比较的元素具有相同的值时应用并集运算。

使用查找操作再次扫描每个元素，计算每个集合的大小，跟踪最大的元素。您将需要存储空间来进行计数。

计算复杂度为 O(MN A^-1(MN,MN)) 其中 A^-1 是反阿克曼函数，可以考虑一个小的对于任何有用的 MN 值，常数 (< 5)。额外的存储复杂度将是 O(MN)。