std :: vector :: push_back拋出分段錯誤

Question

我的程序有問題。對於少量的邊緣它可以很好地工作，但是當它獲得15000個方向圖的邊緣時，我會在運行一分鐘後出現分段錯誤。調試器說它是由vector_back_back方法拋出的。是否有人知道代碼有什麼問題，以及如何避免它？

dfs程序在行result.push_back（tmpResult）中拋出錯誤;

#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會導致堆棧溢出（表現爲平臺上的段錯誤）。

要麼使用更大的堆棧大小（特定於編譯器）來構建程序，要麼在此場景中不使用遞歸。

Answer 2

如果輸入push_back，很可能是因爲您的程序內存不足。由於您沒有捕獲任何異常，因此將調用默認異常處理程序並終止應用程序。在gdb中，您可以使用catch throw命令停止每個「throw」語句。

Answer 3

這很可能是您遞歸太深，導致堆棧溢出。在大多數平臺上，堆棧的大小是固定的;你可能會做得更大，但你可能仍然無法支持任意大的圖表。

也許你可以用迭代算法替換遞歸，維護你自己的堆棧（例如std::stack）你需要在回溯時恢復的狀態。然後，圖形大小的唯一限制是可用內存。