algorithm - Scala - 计算强连接组件 - 堆栈溢出错误

Question

我目前正在学习 Tim Roughgarden 在 Coursera 上的算法专业，第 2 单元第 1 周的作业涉及计算图中强连通分量的大小。我可以为较小尺寸的图计算它们，但问题有大约 500 万条边。我得到了一个运行速度相当快的解决方案，但我花了几个小时试图让它在整个集合上运行，我没有花时间在 AWS super 计算机上，谁能帮我找到解决这个堆栈溢出错误的方法？

我已经离开了预处理步骤，我将数组放入邻接列表并以正确的顺序将其传递到 master_dfs。

import scala.io.Source

object Main extends App {

  def dfs(adjList: Map[Int, List[Int]], currentNode: Int,
          foundNodes: Set[Int], finishingTime: List[Int]): (Set[Int], 
                                                           List[Int]) = {

    val foundsWithCurrent: Set[Int] = foundNodes + currentNode

    val edges: List[Int] = adjList(currentNode)

    val crossOver: List[Int] = edges.filterNot(node => 
                                       foundNodes.contains(node))

    if (crossOver.nonEmpty) {
       val (nextStepFinds, nextStepFinishers) = 
          dfs(adjList, crossOver.head, foundsWithCurrent, finishingTime)

       dfs(adjList, currentNode,
          nextStepFinds, nextStepFinishers)
    }

    else (foundsWithCurrent, currentNode :: finishingTime)

    }


  def master_dfs(orderOfExecution: List[Int], adjList: Map[Int, 
    List[Int]], foundNodes: Set[Int], finishedList: List[Int], sccs: 
    List[List[Int]]): (Set[Int], List[Int], List[List[Int]]) = {

    val (foundThisPass, finishers) = dfs(adjList = adjList,
      currentNode = orderOfExecution.head, foundNodes = foundNodes, 
      finishingTime = finishedList)

    val scc: List[Int] = finishers.filterNot(node => 
    finishedList.contains(node))

    val leftToExecute = orderOfExecution.filterNot(node => 
    foundThisPass.contains(node))

    if (leftToExecute.isEmpty) {
        (foundThisPass, finishers, scc :: sccs)
      }

    else {
       master_dfs(orderOfExecution = leftToExecute, adjList = adjList,
       foundNodes = foundThisPass, finishedList = finishers, sccs = 
                                   scc :: sccs)
      }

  }

Answer 1

由于大多数语言的堆栈空间都是有限的，因此在递归实现算法时，您始终需要考虑要使用多少堆栈空间。

当您知道搜索深度(即到任何节点的最大路径长度)有限时，可以在树或 DAG 上递归实现 DFS。

然而，在一般的有向图或无向图上，图中最长的路径可能包含图中大部分顶点，递归 DFS 实现的调用深度可以与该路径一样长。这可能会导致大量输入的堆栈溢出。

当您不确定所有输入图是否足够浅以确保安全时，您应该使用堆栈对象迭代地实现 DFS，而不是递归地使用调用堆栈。

由于堆栈对象没有调用堆栈那样的限制，迭代实现可以处理更大的输入。