查找矩阵中最大的连接树

假设我有一个矩阵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的最小生成树算法，但是对于这个例子）。

来源

2010-08-30 Julianne T.

将物品的群组称为“岛屿”会不会更好 - 假设你已经把所有的1降到了第一个矩阵的LHS - 这个1仍然算作'树'吗？ – 2010-08-30 22:39:36

当然，右边最大的树是由'0'节点组成的？ – 2010-08-30 22:40:51

@Stephen - 是的，它看起来就是这样 - 除非这不被认为是一棵树。 – 2010-08-30 22:41:31

实际上，您要查找的是Connected组件。 连接组件是一组节点，您可以从任何节点到达该组件内的任何其他节点，其中包括。

连接组件通常适用于图。可以使用BFS/DFS找到连接的组件，并且从给出邻接矩阵输入的算法复杂性角度来看，没有更好的方法来实现这一点。该算法的运行时间为O(N^2)，其中N是图中的一些节点。

在你的情况图中有更多的约束，比如每个节点最多可以相邻4个其他节点。使用BFS/DFS，这会使您的运行时间为O(4N) = O(N)，其中N是多个节点。不可能有更好的复杂性算法，因为在最坏的情况下，您需要考虑每个节点至少一次。

来源

2010-08-30 23:06:02 Leonid

我很想试着回答这个问题，理由是其中的一些陈述是错误的 - 显然是如此。然而，纠正这些陈述的一些明智的编辑可以在一定程度上恢复答案。如果我有魔咒，我会自己做这些修改。 – bbadour 2010-08-31 17:27:19

我修改了答案，感谢您将注意力集中在它上面。我从第一次阅读中误解了这个问题。请随时提出更多改进建议！ – Leonid 2010-08-31 20:29:23

既然你提到Connected Components，你可以包含一个链接到http://en.wikipedia.org/wiki/Connected_component_(graph_theory)#Algorithms 你可以替换false语句“running time ... is O（N^2 ）......“真正的陈述如”运行时间和额外存储都是O（N）...“你可以删除关于”禁忌“的无稽之谈。一旦清理完毕，我会很乐意删除我的评论。事实上，如果我有mojo编辑你的答案，我只是把它清理干净。 – bbadour 2010-08-31 23:58:40

您正在寻找不相交集，所以我会建议一个并查集和查找/联合算法：

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

工会操作是对称的，所以你真的只需要比较各当比较元素具有相同的值时，矩阵的元素与其邻居的右边及其邻居应用联合操作。

使用查找操作再次扫描每个元素来计算每个集合保持最大跟踪的大小。你将需要存储的数量。

计算复杂度将是O（MN甲^-1（MN，MN）），其中A ^-1是逆阿克曼函数，其中之一可以考虑为任何有用的值小的常数（< 5）的MN。额外的存储复杂度将是O（MN）。

来源

2010-08-31 01:26:43 bbadour

不相交集合比BFS/DFS复杂一点，想知道是否有任何理由在BFS/DFS上使用不相交集合来解决问题？ – Leonid 2010-08-31 20:30:20

教育学。原来的问题已经提供了DFS作为解决方案，并询问提问者可能不知道的其他解决方案。提问者提到了Kruskal算法，它比Disjoint Sets更加超线性，并且对于所有实际的目的，Disjoint Sets的big-O复杂度等同于DFS。但是，我怀疑我的最佳DFS将会胜过我所有N的最佳Disjoint Sets解决方案。 – bbadour 2010-08-31 23:46:07

查找矩阵中最大的连接树

回答

相关问题