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

Question

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

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

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

现在我正在使用一个类而不是一个函数来完成它，并跟踪迄今为止在 Set 中已检查的内容，但为了简单起见，我希望将其保留在一个函数中。

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

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

标签： javaalgorithmgraph-algorithm

Answer 1

精简版

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

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

一个很好的视频解释了我发现的算法是如何工作的：YouTube 上的深度优先搜索

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

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

与您的具体问题相关的更多细节

检测邻居

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

您不必为程序中的任何其他内容使用这样的二维数组。我很有信心它会使大量方块的速度更快。

当然，还有其他数据结构可以很容易地查找图节点之间的交叉点。例如，您可以构建一次邻接矩阵并将其用于任何后续计算，但您不必这样做。

使用您的示例运行 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) 没有未探索的邻居，它将像每个后续类型一样从堆栈中弹出，因为没有未探索的邻居。