c# - 将递归 Tarjan 转换为迭代以查找 SCC

Question

所以我已经成功实现了一个递归 tarjan，它为我提供了一个图的 SCC

我的递归实现如下：

public void DFSRecursive(long currentNode){
    low[currentNode] = preCount++;
    visited[currentNode] = true;
    stack.Push(currentNode);                                                                                                                 
    long minimum = low[currentNode];    
    foreach(long successorNode in SuccessorMap[currentNode])
    {
        if(!visited[successorNode])
        {
            DFSRecursive(successorNode);                 
        }
        if(low[successorNode] < minimum)
        {
        minimum = low[successorNode];
        }
    }
    if(minimum < low[currentNode])
    {
        low[currentNode] = minimum;
        return;
    }
    List<long> component = new List<long>();
    long stackTop;
    do
    {
        stackTop = stack.Pop();
        component.Add(stackTop);
    } 
    while(stackTop != currentNode);
    SCComponent.Add(component);
}

现在我需要将其转换为迭代解决方案。我已经检查了很多资源来帮助我，包括一个非常相似的 SO 问题（Tarjan 算法的非递归版本）。我不能使用枚举器，因为我必须处理长值并且当前状态的后继索引已存储在 Dictionary(SuccessorMap[]) 中（需要处理节点数 > 50 亿的图）。

我遵循了将递归解决方案转换为迭代解决方案的一般准则：

1. 将递归调用替换为推送到本地堆栈
2. 用本地堆栈中的弹出替换“返回”

3. 在循环开始时设置变量并从本地堆栈中弹出

   public void DFSIterative(long currentNode)
   {
       var internalStack = new Stack<long>();
       low[currentNode] = preCount++;          
       stack.Push(currentNode);
       long minimum = low[currentNode];
       internalStack.Push(currentNode);
   
       while(!(internalStack.Count == 0))
       {
         currentNode = internalStack.Pop();
         visited[currentNode] = true;
         foreach(long successorNode in SuccessorMap[currentNode])
         {
           if(!visited[successorNode])
           {
             internalStack.Push(successorNode); 
           }
           if(low[successorNode] < minimum)
           { 
             minimum = low[successorNode];
           }
         }
         if(minimum < low[currentNode])
         {
           low[currentNode] = minimum;
           return;
         }
      }
      List<long> component = new List<long>();
      long stackTop;
      do
      {
        stackTop = stack.Pop();
    component.Add(w);
      }
      while(stackTop != currentNode);
   
      SCComponent.Add(component);
      }
   

我认识到迭代方法中的 do-while 循环总是会抛出 a InvalidOperationException(stack empty)，但我还没有弄清楚迭代地实现递归 do-while 。

非常感谢任何帮助我的帮助。