堆棧溢出深度優先搜索

我正在編寫一個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上做得更好？

來源

2017-01-16 Newb

用循環替換遞歸併使用顯式堆棧（任何列表都可以）。

堆棧將模擬調用堆棧，但不會如此緊密有界。

請參閱從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

來源

2017-01-16 12:34:10

堆棧溢出深度優先搜索

回答

相關問題