std :: vector :: push_back이 세그먼트 화 오류를 throw합니다.

Question

내 프로그램에 문제가 있습니다. 작은 수의 가장자리에 대해서는 완벽하게 작동하지만 방향 그래프의 가장자리가 15000 개가되면 1 분 런타임 후에 세그먼트 오류가 발생합니다. 디버거는 벡터 푸시 백 메소드에 의해 throw됩니다. 누군가가 코드에 무엇이 잘못되었는지, 어떻게 피하는 지 알고 있습니까?

result.push_back (tmpResult)에서 dfs 프로 시저에 오류가 발생했습니다.는

#include <cstdlib> 
#include <iostream> 
#include <vector> 

using namespace std; 

typedef struct { 
    unsigned int endNode;  // Number of dest node 
    bool used;     // true, if edge was used in dfs 
} EdgeType; 

typedef struct { 
    unsigned int startNode;  // Number of source node 
    vector<EdgeType> edge;  // Outgoing edges from node 
} NodeType; 

typedef struct { 
    unsigned int startNode; 
    unsigned int endNode; 
} ResultType; 


bool loadInput(vector<NodeType>& graph, unsigned int& numEdges); 
void dfs(vector<NodeType>& graph, unsigned int i, unsigned int numEdges, vector<ResultType>& result); 

int main(int argc, char** argv) { 
    vector<NodeType> graph; 
    vector<ResultType> result; 
    unsigned int numEdges; 

    result.reserve(300000); 

    // Generate oriented multigraph (3 nodes, 150000 edges) 
    numEdges = 150000; 
    NodeType tmpNode; 
    EdgeType tmpEdge; 

    for (unsigned int i = 0; i < 50000; i++) { 
     tmpEdge.used = false; 
     tmpEdge.endNode = 1; 
     tmpNode.edge.push_back(tmpEdge);  
    } 
    tmpNode.startNode = 0; 
    graph.push_back(tmpNode); 
    tmpNode.edge.clear(); 

    for (unsigned int i = 0; i < 50000; i++) { 
     tmpEdge.used = false; 
     tmpEdge.endNode = 2; 
     tmpNode.edge.push_back(tmpEdge);  
    } 
    tmpNode.startNode = 1; 
    graph.push_back(tmpNode); 
    tmpNode.edge.clear(); 

    for (unsigned int i = 0; i < 50000; i++) { 
     tmpEdge.used = false; 
     tmpEdge.endNode = 0; 
     tmpNode.edge.push_back(tmpEdge);  
    } 
    tmpNode.startNode = 2; 
    graph.push_back(tmpNode); 
    tmpNode.edge.clear(); 

    cout << "numEdges: " << numEdges << endl; 

    // Find way 
    for (unsigned int i = 0; i < graph.size(); i++) { 
     dfs(graph, i, numEdges, result); 
    } 

    // No way found 
    cout << "-1" << endl; 

    return 0; 
} 

void dfs(vector<NodeType>& graph, unsigned int i, unsigned int numEdges, vector<ResultType>& result) { 
    // Way was found, print it and exit program (bad style, only for testing) 
    if (numEdges == result.size()) { 
     cout << graph.size() << endl; 
     vector<ResultType>::iterator it; 
     for (it = result.begin(); it != result.end(); it++) { 
      cout << (*it).startNode << " " << (*it).endNode << endl; 
     } 
     cout << "0 0" << endl; 
     exit(0); 
    } 
    // For each outgoing edge do recursion 
    for (unsigned int j = 0; j < graph[i].edge.size(); j++) { 
     if (i >= graph.size()) return; 
     if (!graph[i].edge[j].used) { 
      graph[i].edge[j].used = true; 
      ResultType tmpResult; 
      tmpResult.startNode = graph[i].startNode; 
      tmpResult.endNode = graph[i].edge[j].endNode; 
      result.push_back(tmpResult); 
      dfs(graph, graph[i].edge[j].endNode, numEdges, result); 
      result.pop_back(); 
      graph[i].edge[j].used = false; 
     } 
    } 
} 

내 프로그램 나를 위해 목표는 각 에지는 한 번만 사용 중심의 그래프에서 방법을 찾아야하는 것입니다.

Answer 1

dfs은 반복적으로 호출합니다. numEdges을 늘리면 재귀 수준이 증가하므로 결과적으로 numEdges이 증가하면 스택 오버플로가 충분히 발생합니다 (플랫폼에서 Segfault로 나타남).

큰 스택 크기 (컴파일러 관련)로 프로그램을 빌드하거나이 시나리오에서는 재귀를 사용하지 마십시오.

Answer 2

push_back이 throw되는 경우 프로그램에서 메모리가 부족한 것이 원인 일 가능성이 큽니다. 예외를 catch하지 않으므로 기본 예외 처리기가 호출되고 응용 프로그램이 종료됩니다. gdb에서 catch throw 명령을 사용하여 모든 "throw"문을 중지 할 수 있습니다.

Answer 3

스택 오버플로를 유발할 가능성이 너무 큽니다. 대부분의 플랫폼에서 스택의 크기는 고정되어 있습니다. 당신은 그것을 더 크게 만들 수 있을지도 모르지만, 당신은 아마도 임의로 큰 그래프를 지원할 수 없을 것입니다.

아마도 반복 알고리즘을 사용하여 재귀를 대체하고 역 추적 할 때 복원해야하는 상태 (예 : std::stack)를 유지할 수 있습니다. 그래프 크기에 대한 유일한 제한은 사용 가능한 메모리입니다.