高效算法寻找连通组件

Question

现在我有一个带有4列和无限行的网格。每个单元格可以用一个正方形占据，这些正方形存储在ArrayList<Square> squares中。

我想要能够找到所有与所选正方形连接（通过边缘/角落）的正方形，如下图所示：

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

现在我使用一个类而不是函数来完成它，并在集合中跟踪已经检查过的正方形，但出于简单起见，希望将其保留在函数中。

我该采取哪些步骤来实现高效的算法？

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

- Sarah

---

请参阅https://meta.stackoverflow.com/questions/284236/why-is-can-someone-help-me-not-an-actual-question ...我们只帮助解决具体的问题。在某种程度上，您的请求就像是说：“有人坐下来跟我解释如何解决这个问题。” 这不是本社区的初衷。 - GhostCat

你需要一个良好的八连通洪水填充算法的实现。 - MBo

请描述正方形是如何存储的。坐标列表还是二维数组？ - user1196549

它们被存储在坐标的ArrayList中。当我想要查找相邻的正方形时，我执行碰撞检测以查看是否有任何相邻的正方形。 - Sarah

“squares” 是否按 Y 坐标排序？ - MBo

Answer 1

简短版

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

在你的情况下，每个方块可以被看作是图的一个节点，如果它们共享一条边或一个角，那么它们之间存在一条边。

我找到了一段很好的视频，解释了这个算法的工作原理：Depth First Search on youtube

DFS算法可能与你尝试使用递归方法的方式非常相似，但关键的区别在于，在算法进行时，你会“着色”所访问的节点/方块。建议你将探索过的节点作为每个方块的属性，而不是将其保存在单独的数据结构中。

然后，如果你遇到了一个已经访问过的方块，就不要再去探索它了。如果你已经探索完了当前节点的所有邻居，就回到你之前正在探索的节点，并继续探索它的邻居（递归），直到你回溯到从哪里开始算法的节点。

与你的特定问题相关的更多细节

检测邻居

你提到你的正方形存储在ArrayList中，这很好。但是它并不能防止你构建一个二维正方形数组，其中如果没有正方形，则单元格为null；如果有正方形，则包含位于该位置的正方形实例的引用。依我之见，这将使查找邻居比查找每对正方形之间的碰撞容易得多（我认为这是你现在正在做的事情）。

您不必在程序中使用这样的二维数组。我非常有信心，这会让大量正方形的操作更快。

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

使用您的示例运行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,2)]

栈顶是(1,2)。

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

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

第二步：

栈：[(1,2) (2,2)]

栈顶是(2,2)。

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

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

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

第三步：

栈：[(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)没有未探索的邻居，它将从栈中弹出，因为没有剩余未探索的邻居。

- Patrick

---

广度优先搜索也可以。 - oleg.cherednik

在研究了深度优先搜索算法之后，似乎大多数示例都使用树。只是为了确保我走上了正确的道路，您怎样才能在基于网格/块的系统中最好地实现它呢？ - Sarah

我编辑了我的回答，试图更好地回答你的问题。 - Patrick

Answer 2

我同意评论中的观点，认为你在提问时应该更具体。然而，既然你问到了“有些方块被检查两次”的部分，我可以回答这一部分。您可以维护矩阵以跟踪已经访问过的单元格。最初，所有单元格都可以设置为0。处理给定单元格后，您可以将其设置为1。每次处理任何单元格时，只需使用visited matrix检查它是否已经被访问过即可。

 int visited[][] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } };
 // you logic to process cell
if (visited[x][y] ==0) // check is not visited
 visited[x][y] = 1; // mark cell as visited
else 
 //skip

- Rishi Saraf

Answer 3

基本上我认为没有必要实现任何复杂的算法，因为网格中的邻居很容易计算，例如

 +-------+-------+-------+
 |x-1,y+1|  x,y+1|x+1,y+1|
 +-------+-------+-------+
 |x-1,  y|  x,  y|x+1,  y|
 +-------+-------+-------+
 |x-1,y-1|  x,y-1|x+1,y-1|
 +-------+-------+-------+

你可以将 squares 存储在类似于 List<List<Square>> 的数据结构中，并通过索引访问它们。

但是，如果你想将它们存储在简单的 List<> 中，你仍然可以通过计算第 n 个元素的索引来实现。

+----->
| [(0,0) - 0  ]   [(1,0) - 1st]   [(2,0) - 2nd]   [(3,0) - 3th]
| [(0,1) - 4th]   [(1,1) - 5th]   [(2,1) - 6th]   [(3,1) - 7th]
v [(0,2) - 8th]   [(1,2) - 9th]   [(2,2) -10th]   [(3,2) -11th]

// index for (2,1)
index_of_2_1 = (y * rows_count) + x = (1*4) + 2 = 6

- puffy.bun