C++ - 如何增加堆栈大小以允许更多的递归,以便Kosaraju的算法计算强连通组件

Question

我使用的是mac,4GB的RAM和CLion IDE.编译器是Clang.我需要在Depth First Search的递归实现中允许更多的递归(目前在具有80k节点的图形上失败).

typedef unordered_map <int, vector<int>> graph;
void DFS (graph &G, int i, vector <bool> &visited) {

    visited[i] = true;
    for (int j = 0; i < G[i].size(); j++) {
        if (!visited[G[i][j]]) {
            DFS(G, G[i][j], visited);
        }
    }
    t++;
    finishingTime[t] = i; //important step
}

这是为了实现Kosaraju算法来计算图中强连通分量.https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm我知道可以将DFS实现为迭代,但最后一步很重要,我找不到使用迭代包含它的方法.这是因为当DFS失败并且发生回溯时,该步骤完成,并且递归提供了一种非常自然的方式来执行此操作.

所以目前我只有两个选择:

• 增加堆栈大小以允许更多递归
• 或者找到一个迭代的解决方案

任何想法怎么做？

Answer 1

正如注释所建议的，您可以将对 DFS 的每次调用放在由 DFS 参数列表创建的堆上分配的堆栈上，然后迭代堆栈。堆栈中的每个条目本质上都是一个任务。

类似伪代码：

Start and run "recursion":
nr_of_recursions = 0;
dfs_task_stack.push(first_task_params)
while dfs_task_stack not empty
  DFS(dfs_task_stack.pop)
  nr_of_recursions += 1
end while;
true_finishingtime[] = nr_of_recursions - finishingtime[];

DFS:
for each recursion found
  dfs_task_stack.push(task_params)
end for;
t++; finishingtime...

不确定你的算法，但将任务推送到堆栈的顺序可能很重要，即“对于每个......”的顺序。

我冒昧地重新定义了“完成时间”的反义词。要获得原始定义，请用所做的递归总数减去新的完成时间。