java - 二维数组深度优先搜索

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) 使用矩阵探索 u 的“1”个邻居。

然而，问题来了，DFS(u, U) 还从 U 中删除了所有发现的元素。

很容易理解和证明该算法确实总是在 O(n * log n) 内完成。从树集中删除一个元素的最坏情况复杂度为 O(log n)。每个 DFS(u, U) 运行最多可以访问 |U| 个元素，并且通过任何方式访问的每个元素都会从 U 中删除，因为执行进展。当 U 变为空时，算法终止。

简短摘要

例如，无论您之前获得的知识如何，都可以通过在每个元素上运行 DFS 来生成 O(n^2) 算法。使用任何确保您不在已发现的组/岛上运行 DFS 的机制都可能产生更好的算法。

抱歉，我不能直接分析你自己的算法，但这可能会帮助你自己做。