连接图的 C++ 递归

Question

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

//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;
}

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

提前致谢!

Answer 1

这个解决方案不会起作用，因为它混淆了“遍历”和“事件/连接”的概念。两者是正交的:例如，一个单元格可能处于非事件状态且已遍历，或者处于事件状态但未遍历。伪代码顶部的 if 语句为两者返回 true，这是不正确的。

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

最后，解决方案不需要是递归的:您可以通过直接的 Breadth-first search 来完成您需要的。 ，这可以通过队列而不是递归来完成。