std :: vector :: push_back генерирует ошибку сегментации

Question

У меня проблема с моей программой.Для небольшого числа ребер это работает отлично, но когда он получает 15000 ребер ориентированного графа, я получаю ошибку сегментации после одной минуты выполнения.Отладчик говорит, что он вызывается векторным методом push_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 в достаточной мере вызывает переполнение стека (что проявляется в качестве ошибки на вашей платформе).

Либо создайте программу с большим размером стека (compiler-или не используйте рекурсию в этом сценарии.

Answer 2

Скорее всего, вы используете слишком глубоко, вызывая переполнение стека.На большинстве платформ стек имеет фиксированный размер;возможно, вы сможете увеличить его, но, вероятно, все равно не сможете поддерживать произвольно большие графы.

Возможно, вы могли бы заменить рекурсию итерационным алгоритмом, поддерживая свой собственный стек (например, * 1003).*) состояния, которое необходимо восстановить при возврате.Тогда единственным ограничением размера графа является доступная память.

Answer 3

Если push_back выбрасывает, это, скорее всего, потому, что вашей программе не хватает памяти. Поскольку вы не перехватываете какие-либо исключения, вызывается обработчик исключений по умолчанию, и приложение завершается. В gdb вы можете использовать команду catch throw для остановки при каждом операторе throw.