Stack Overflow 深度优先搜索

Question

我正在写一个 DFS 连接组件标签，基本思想很简单，只需将 DFS 递归地应用于四个邻居（左，右，上，下）。

问题是当连接区域太大时，比如 100 * 100 像素，它会出现运行时错误，

0xC00000FD: Stack overflow (:  0x00000001, 0x001D2EB4)

我觉得是因为太深了。这个有什么优化或者解决办法吗？

代码如下：

void DFS_Traversal(cv::Mat &InputMat, cv::Mat &LabelMat, cv::Point2i cur_SP, int Thresh, int cur_Label){

    if (cur_SP.y > 2 && cur_SP.y < (InputMat.rows - 2) && cur_SP.x > 2 && cur_SP.x < (InputMat.cols - 2)){
        uchar* pre_Input_rowPtr = InputMat.ptr<uchar>(cur_SP.y - 1);
        uchar* cur_Input_rowPtr = InputMat.ptr<uchar>(cur_SP.y);
        uchar* next_Input_rowPtr = InputMat.ptr<uchar>(cur_SP.y + 1);
        uchar* pre_Label_rowPtr = LabelMat.ptr<uchar>(cur_SP.y - 1);
        uchar* cur_Label_rowPtr = LabelMat.ptr<uchar>(cur_SP.y);
        uchar* next_Label_rowPtr = LabelMat.ptr<uchar>(cur_SP.y + 1);

        //cur_Label_rowPtr[cur_SP.x] = cur_Label;

        //Left Point
        if ( cur_Label_rowPtr[cur_SP.x - 1] == 0 && std::abs(cur_Input_rowPtr[cur_SP.x] - cur_Input_rowPtr[cur_SP.x - 1]) < Thresh){
            cv::Point2i left_Point(cur_SP.x - 1, cur_SP.y);

            cur_Label_rowPtr[cur_SP.x - 1] = cur_Label;
            DFS_Traversal(InputMat, LabelMat, left_Point, Thresh, cur_Label);
        }
        //Right Point
        if ( cur_Label_rowPtr[cur_SP.x + 1] == 0 && std::abs(cur_Input_rowPtr[cur_SP.x] - cur_Input_rowPtr[cur_SP.x + 1]) < Thresh){
            cv::Point2i right_Point(cur_SP.x + 1, cur_SP.y);

            cur_Label_rowPtr[cur_SP.x + 1] = cur_Label;
            DFS_Traversal(InputMat, LabelMat, right_Point, Thresh, cur_Label);
        }
        //Up Point
        if ( pre_Label_rowPtr[cur_SP.x] == 0 && std::abs(cur_Input_rowPtr[cur_SP.x] - pre_Input_rowPtr[cur_SP.x]) < Thresh){
            cv::Point2i up_Point(cur_SP.x, cur_SP.y - 1);

            pre_Label_rowPtr[cur_SP.x] = cur_Label;
            DFS_Traversal(InputMat, LabelMat, up_Point, Thresh, cur_Label);
        }
        //Down Point
        if ( next_Label_rowPtr[cur_SP.x] == 0 && std::abs(cur_Input_rowPtr[cur_SP.x] - next_Input_rowPtr[cur_SP.x]) < Thresh){
            cv::Point2i down_Point(cur_SP.x, cur_SP.y + 1);

            next_Label_rowPtr[cur_SP.x] = cur_Label;
            DFS_Traversal(InputMat, LabelMat, down_Point, Thresh, cur_Label);
        }

    }
    return;

}

运行在8G内存的笔记本电脑上，最大不溢出区域为72 * 72，接近5000级递归。如何使用 DFS 做得更好？

Answer 1

用循环替换递归并使用显式堆栈（任何列表都可以）。

堆栈将模拟调用堆栈，但不会如此紧密。

参见 Wikipedia 的迭代实现：

iterativeInorder(node)
  s ← empty stack
  while (not s.isEmpty() or node ≠ null)
    if (node ≠ null)
      s.push(node)
      node ← node.left
    else
      node ← s.pop()
      visit(node)
      node ← node.right

Stack Overflow 深度优先搜索

Stack Overflow in Depth First Search

c++

stack-overflow

depth-first-search

connected-components