0

我使用基于 DFS 的算法来计算大图中的强分量。该算法在小图上运行良好，但我在大图上遇到问题。因此，在 DFS 函数程序的大约 28 K 次递归调用之后，它就会挂起。VS2010 给我一条消息 VS is busy, no crashs no errors。为了弄清楚发生了什么，我打印了一些信息（由于速度低，无法在调试中运行）。我发现程序挂在位置 4 并且没有到达位置 1（观看代码）。

// Main DFS function
void DFS(vector<Edge>& graph, int source_node, bool *vertex_visited, pair<int, int>& direction){

    cout << "\r" << "Position 1" << std::flush;
    // mark vertex as visited
    vertex_visited[source_node - 1] = false;
    // array for all neighbour edges 
    vector<vector<Edge>::iterator> all_neighbours;

    // doesent matter 
    if (direction.second){
        size_of_scc++;
    }

    // binary search of edges incident with source vertex
    pair<vector<Edge>::iterator, bool> itera = find_if_binary_for_edges(graph.begin(), graph.end(), source_node);
    cout << "\r" << "Position 2" << std::flush;

    // push all incident edges to all_neighbours vector
    if (itera.second){
        pair<vector<Edge>::iterator, vector<Edge>::iterator> bounds = find_all_in_range(itera.first, graph);
        vector<Edge>::iterator it = bounds.first;
        while (it != bounds.second){
            all_neighbours.push_back(it++);
        }
    }

    cout << "\r" << "Position 3" << std::flush;

    // if this vertex wasn't visited in the past cal DFS from neighbour vertex
    for (vector<vector<Edge>::iterator>::iterator it = all_neighbours.begin(); it != all_neighbours.end(); ++it){
        if (vertex_visited[(**it)[1] - 1]){
            cout << "\r" << "Position 4" << std::flush;
            DFS(graph, (**it)[1], vertex_visited, direction);
        };
    }

    // need this stuff for SCC computation
    cout << "\r" << "Position 5" << std::flush;
    if (direction.first)
        finishing_times[finishing_times_counter++] = source_node;
}

所以我不知道接下来要做什么，接下来我需要执行哪些调试步骤...？在位置 4 程序必须再次调用 DFS 然后打印“位置 1”但它不会发生。因为它可能是什么？图有大约 857K 个顶点和 5 * 10^6 条边。谢谢。

4

1 回答 1

0

所以这是stackoverflow错误，我第一次没有得到它，但是从DFS列表中删除一些参数后，我遇到了stackoverflowerror。

于 2013-02-19T09:48:33.123 回答