2

我还没有实现任何东西，但我正在考虑使用递归来识别网格中“主动连接”到给定单元格的所有单元格，即“活跃”并通过共享一张脸直接连接的单元格与所讨论的（活动）单元格或更远/间接地通过与其（活动）邻居之一共享一张脸连接。断开连接的发生是因为网格中的某些单元格可能被认为是“不活动的”（无论定义如何）。我的想法/伪代码如下：

//Call function to traverse connections
traverse_connections(cell);

//Traverse function definition
bool traverse_connections(cell) {
  //Check if cell is inactive or traversed - base case
  if (current cell is inactive or traversed) {
     return true;
  }
  //-Mark cell then move on to its neighbors
  Mark cell as traversed and add it to the list of 'actively connected' cells;
  bool ok = true;
  for(neighbor_cell in neighbors of cell) {
     ok &= traverse_connections(neighbor_cell);
  }
  return ok;
}

我认为这涵盖了基本情况，标记了单元格，然后继续对其邻居、邻居的邻居等做同样的事情。这看起来好吗？我是否缺少任何明显的差距？如果有图连接和递归方面的专业知识的人可以参与进来，我将不胜感激。我也很难提出一个迭代等价物。对此的任何想法也将不胜感激。

提前致谢！

4

2 回答 2

2

此解决方案将不起作用，因为它混淆了“遍历”和“活动/连接”的概念。两者是正交的：例如，一个单元格可能是非活动的并且被遍历，或者是活动的并且没有被遍历。if伪代码顶部的语句对true两者都返回，这是不正确的。

您应该将标记已遍历单元格的表格与标记活动单元格的表格分开。在进入递归调用之前，您需要确保一个单元格被标记为已遍历，否则解决方案可能会太慢，甚至会耗尽堆栈。

最后，解决方案不需要递归：您可以通过简单的广度优先搜索来完成您需要的事情，这可以通过队列而不是递归来完成。

于 2013-10-08T14:16:41.057 回答
1

您目前标记单元格的方式很可能会给您带来问题。例如，如果您要标记的这些单元之一具有需要稍后遍历的相邻单元，则它们可能不会被遍历。

如果您研究A* (A-Star) 算法，它应该会让您对图遍历有一个很好的了解。UCS（统一成本搜索）也是另一种使用图遍历的算法。

于 2013-10-08T14:29:30.033 回答