scala – Tarjan的强关联组件算法的功能实现

为了理解算法，可以了解dfs函数的折叠和合约。

def scc[T](graph:Map[T,Set[T]]): Map[T,T] = {
  //`dfs` finds all strongly connected components below `node`
  //`path` holds the the depth for all nodes above the current one
  //'sccs' holds the representatives found so far; the accumulator
  def dfs(node: T,path: Map[T,Int],sccs: Map[T,T]): Map[T,T] = {
    //returns the earliest encountered node of both arguments
    //for the case both aren't on the path,`old` is returned
    def shallowerNode(old: T,candidate: T): T = 
      (path.get(old),path.get(candidate)) match {
        case (_,None) => old
        case (None,_) => candidate
        case (Some(dOld),Some(dCand)) =>  if(dCand < dOld) candidate else old
      }

    //handle the child nodes
    val children: Set[T] = graph(node)
    //the initially known shallowest back-link is `node` itself
    val (newState,shallowestBackNode) = children.foldLeft((sccs,node)){
      case ((foldedSCCs,shallowest),child) =>
        if(path.contains(child))
          (foldedSCCs,shallowerNode(shallowest,child))
        else {
          val sccWithChildData = dfs(child,path + (node -> path.size),foldedSCCs)
          val shallowestForChild = sccWithChildData(child)
          (sccWithChildData,shallowestForChild))
        }
    }

    newState + (node -> shallowestBackNode)
  }

  //run the above function,so every node gets visited
  graph.keys.foldLeft(Map[T,T]()){ case (sccs,nextNode) =>
    if(sccs.contains(nextNode))
      sccs
    else
      dfs(nextNode,Map(),sccs)
  }
}

我已经在Wikipedia页面上的示例图上测试了代码。

与命令版本的区别

与原始实现相反，我的版本避免显式解开堆栈，只需使用正确的(非尾部)递归函数。堆栈由称为路径的持久映射表示。在我的第一个版本中，我使用了一个List作为堆栈;但是由于不得不搜索包含元素，因此效率较低。

效率

代码效率相当高。对于每个边缘，您必须更新和/或访问不可变地图路径，其中O(log | N |)的总和为O(| E | log | N |)。这与命令式版本实现的O(| E |)相反。

线性时间实现

Chris Okasaki的回答中的论文在Haskell中提供了一个线性时间解决方案来寻找强连接的组件。他们的实现是基于Kosaraju的算法，用于查找SCC，它基本上需要两次深度优先遍历。本文的主要贡献似乎是Haskell中的一个懒惰的线性时间DFS实现。

实现线性时间解决方案所需要的是具有O(1)单例添加和成员资格测试的集合。这基本上是同样的问题，使得该答案中给出的解决方案具有比命令式解决方案更高的复杂性。他们使用Haskell中的状态线程来解决它，这也可以在Scala中完成(请参阅Scalaz)。因此，如果愿意使代码变得复杂，可以将Tarjan的SCC算法实现为功能性O(| E |)版本。