C++-如何增加堆栈大小以允许 Kosaraju 算法进行更多递归以计算强连通分量

Question

我使用的是 mac、4GB RAM 和 CLion IDE。编译器是 Clang。我需要在这个深度优先搜索的递归实现中允许更多的递归(目前在具有 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...

不确定您的算法，但您将任务推送到堆栈的顺序可能很重要，即“for each ...”的顺序。

我冒昧地将“finishingtime”的含义重新定义为它的倒数。要获得原始定义，请用递归总数减去新的完成时间。