java - 查找连通分量的高效算法

Question

现在我有一个包含 4 列和无限行的网格。每个单元格可能被一个 Square 占据，Square 存储在 ArrayList<Square> squares 中。 .

我希望能够找到所有连接(通过边/角)到选定正方形的正方形，例如:



我正在使用递归函数来检查所选正方形周围的正方形，然后对这些正方形执行相同的操作，但这会导致某些正方形被检查两次并且效率低下。

现在我正在使用一个类而不是一个函数来完成它，并跟踪到目前为止在 Set 中已检查过的那些，但为了简单起见，我想将它保留在一个函数中。

我可以采取哪些步骤来实现有效的算法？

更新 :正方形存储在 ArrayList 中，而不是 2D 数据结构中，因为我需要它们可以在程序的其他地方轻松访问。当我需要找到相邻的方块时，我会测试方块之间的碰撞。

Answer 1

短版

我认为深度优先搜索算法可能对您有所帮助。

在您的情况下，每个图块都可以视为图形的一个节点，如果两个节点共享边或角，则它们之间存在边。

一个很好的视频解释了我发现的算法是如何工作的:Depth First Search on youtube

DFS 算法可能与您使用递归方法尝试的算法非常相似，但关键的区别在于您在算法中“着色”了您访问的节点/图块。与其将探索的节点保留在单独的数据结构中，我建议您将其作为每个图块的属性。

然后，如果您偶然发现已经访问过的图块，则不会对其进行探索。如果您已经探索了当前节点的所有邻居，您将返回到您之前探索的节点并探索其邻居(递归)，直到您回溯到您开始算法的节点。

与您的具体问题相关的更多详细信息

检测邻居

您提到您的方块存储在 ArrayList 中。这可以。但是，如果没有正方形或包含对位于该位置的正方形实例的引用，则它不会阻止您构建其单元格为空的 2D 正方形数组。在我看来，这将使寻找邻居比寻找每对正方形之间的碰撞容易得多(我认为这就是您现在正在做的事情)。

您不必将这样的二维数组用于程序中的其他任何内容。我非常有信心它会使大量正方形的事情变得更快。

当然，还有其他数据结构可以轻松查找图形节点之间的交集。例如，您可以构建一个 adjacency matrix一次并将其用于任何后续计算，但您不必这样做。

使用您的示例运行 DFS

我将使用堆栈来跟踪我在瓷砖探索中的位置。我将通过它们的坐标来引用样式。我们开始算法的单元格在您的图中以红色着色，并具有坐标 (1,2)。

算法如下:

while (!stack.isEmpty()) {
  currentTyle = stack.top();
  boolean currentHasNeighborsToExplore = false;
  for (n in neighbors of currentTyle) {
    if (n is not explored) {
      n is explored;
      stack.add(n);
      currentHasNeighborsToExplore = true;
      break;
    }
  }
  if (!currentHasNeighborsToExplore) {
    stack.pop();
  }
}

我们从您的初始类型 (1,2) 开始算法。

第 1 步

堆栈:[(1,2)

栈顶是 (1,2)

(1,2) 有邻居 n: (2,2) 这是未开发的

(2,2) 现在已被探索，我们将其添加到堆栈中并进行下一步

第 2 步

堆栈:[(1,2) (2,2)

栈顶是 (2,2)

(2,2) 有邻居 n: (1,2) 被探索

(2,2) 有邻居 n: (3,1) 这是未开发的

(3,1) 现在已被探索，我们将其添加到堆栈中并进行下一步

第 3 步

堆栈:[(1,2) (2,2) (3,1)

栈顶是 (3,1)

(3,1) 有邻居 n: (2,2) 被探索

(3,1) 有邻居 n: (4,2) 这是未开发的

(4,2) 现在已被探索，我们将其添加到堆栈中并进行下一步

第 4 步

堆栈:[(1,2) (2,2) (3,1) (4,2)

栈顶是 (4,2)

(4,2) 有邻居 n: (4,3) 这是未开发的

(4,3) 现在已被探索，我们将其添加到堆栈中并进行下一步

第 5 步

堆栈: [(1,2) (2,2) (3,1) (4,2) (4,3)

栈顶是 (4,3)

(4,3) 有邻居 n: (4,2) 被探索

(4,3) 没有未探索的邻居，我们将其从堆栈中弹出并进行下一步

第 6 步

堆栈:[(1,2) (2,2) (3,1) (4,2)

栈顶是 (2,2)

(4,2) 有邻居 n: (4,3) 被探索

(4,2) 有邻居 n: (5,1) 这是未开发的

(5,1) 现在已被探索，我们将其添加到堆栈中并进行下一步

下一步

在下一步中，(5,1) 没有未探索的邻居，它将像每个后续类型一样从堆栈中弹出，因为没有未探索的邻居留下。