在矩阵中查找最大的连通树
假设我有一个矩阵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个节点。
我知道我大概可以做一个简单的深度优先搜索，但是我想知道是否有一些众所周知的我错过了，也许在图论的领域（比如克鲁斯卡尔的最小生成树算法，但是对于这个例子）。
有效地，您要查找的是Connected组件。 连接组件是一组节点，您可以从任何节点到该组件内的其他节点。
连接的组件通常适用于图形。 使用BFS/DFS可以找到连接的组件，并且从算法复杂度的角度给出邻接矩阵输入，没有更好的方法来做到这一点。 该算法的运行时间为O(N^2) ，其中N是图中节点的数量。
在你的情况图中有更多的约束，比如每个节点最多可以与其他4个节点相邻。 使用BFS/DFS ，这会使您的运行时间为O(4N) = O(N) ，其中N是多个节点。 不可能有更好的复杂性算法，因为在最坏的情况下，您需要考虑每个节点至少一次。
你正在寻找不相交的集合，所以我会建议一个不相交集数据结构和一个查找/联合算法：
请参阅http://en.wikipedia.org/wiki/Disjoint-set_data_structure#Disjoint-set_forests
联合运算是对称的，因此当比较元素具有相同的值时，您只需要将矩阵的每个元素与其右侧的相邻元素和下面的相邻元素进行比较，即可应用联合运算。
使用查找操作再次扫描每个元素以计算每个集合保持最大轨迹的大小。 你将需要存储的数量。
计算复杂度为O（MN A-1（MN，MN）），其中A-1是逆阿克曼函数，对于MN的任何有用值，可以考虑一个小常数（<5）。 额外的存储复杂度将是O（MN）。
链接地址: http://www.djcxy.com/p/63791.html