Scala中的圖遍歷

Question

我知道的圖遍歷（DFS和BFS）實現使用可變的一組「被訪問」頂點。你將如何實現它們只有不可變的數據結構？我看到this question。現在，我不知道是否還有其他的解決方案

Answer 1

下面是做到這一點的一種方法：

def traverse[A](graph : Map[A,Set[A]], toVisit : Seq[A], visited : Set[A]) : Seq[A] = { 
    if(toVisit.isEmpty) { 
    Seq.empty 
    } else { 
    val next = toVisit.head 
    val succ = (graph(next) -- visited -- toVisit).toSeq 
    // DFS : 
    // next +: traverse(graph, sucC++ toVisit.tail, visited + next) 
    // BFS : 
    next +: traverse(graph, toVisit.tail ++ succ, visited + next) 
    } 
} 

def traverseFrom[A](graph : Map[A,Set[A]], initial : A) = 
    traverse(graph, Seq(initial), Set.empty) 

訣竅很簡單，就是繞過節點列表訪問（這將符合您的堆棧或隊列在命令式算法中）以及訪問狀態集合。

如果你擔心調用棧與每個遞歸調用越來越大，你把它尾遞歸通過使用一個額外的參數：好像你寫

@annotation.tailrec 
def traverseTR[A](graph : Map[A,Set[A]], toVisit : Seq[A], visited : Set[A], accumulator : Seq[A]) : Seq[A] = { 
    if(toVisit.isEmpty) { 
    accumulator 
    } else { 
    val next = toVisit.head 
    val succ = (graph(next) -- visited -- toVisit).toSeq 
    // DFS : 
    //traverseTR(graph, sucC++ toVisit.tail, visited + next, accumulator :+ next) 
    // BFS : 
    traverseTR(graph, toVisit.tail ++ succ, visited + next, accumulator :+ next) 
    } 
} 

def traverseFrom[A](graph : Map[A,Set[A]], initial : A) = 
    traverseTR(graph, Seq(initial), Set.empty, Seq.empty) 

這會給你一個版本一樣高效它使用一個while循環。

Answer 2

以前的解決方案有幾個問題：

這是一種低效：（圖表（下） - 訪問 - toVisit）.toSeq可能是圖形的大小呈線性關係。

的DFS版本不正確，因爲它沒有根據DFS順序訪問： 例如，如果你有以下圖表：

地圖（「A」 - >設置（「B」，「d 「），」B「→Set（」C「，」D「），」C「→Set（），」D「→Set（」E「），」E「→Set（））

然後，如果你運行DFS從A開始，法律DFS訪問命令是：

A，B，C，d，E A，B，d，E，C A，d，E，B ，C

上述算法可能訪問的頂點在下面非法命令： A，d，B，C，E

由於在第一次迭代中添加都 d和B到toVisit序列。

Answer 3

以下代碼會執行一些有向圖遍歷。 它只使用不可變的數據結構，並且是遞歸的，但有一些成本：

List toVisit可能包含許多重複項，因爲它包含我們計劃在未來訪問的所有頂點。在最糟糕的情況下，我們可能會在圖表中爲幾乎每個邊添加一個頂點。 因此，尾遞歸的空間複雜度爲，空間複雜度爲爲O（| E | + | V |）。

對於密集圖，空間複雜度爲O（| V |）的標準非尾遞歸解決方案效率更高，即使它確實需要保存長度爲O（| V |）的調用堆棧。由於存儲輸入圖本身需要O（| V | + | E |）空間，所以上述成本可能是可以接受的。 提高上述空間複雜度的一種可能的方法是用List [Iterator [Vertex]]替換爲Visis。由於迭代器被懶惰地評估，這將把空間複雜度降低到O（| V |）。

object DirectedGraphTraversals { 

    type Graph[Vertex] = Map[Vertex, Set[Vertex]] 

    def dfs[Vertex](graph: Graph[Vertex], initialVertex: Vertex) = 
    dfsRec(DfsNeighbours)(graph, List(initialVertex), Set(), Set(), List()) 

    def topologicalSort[Vertex](graph: Graph[Vertex]) = 
    graphDfsRec(TopologicalSortNeighbours)(graph, graph.keySet, Set(), List()) 

    def stronglyConnectedComponents[Vertex](graph: Graph[Vertex]) = { 
    val exitOrder = graphDfsRec(DfsNeighbours)(graph, graph.keySet, Set(), List()) 
    val reversedGraph = reverse(graph) 

    exitOrder.foldLeft((Set[Vertex](), List(Set[Vertex]()))){ 
     case ((visitedAcc, connectedComponentsAcc), vertex) => 
     val connectedComponent = dfsRec(DfsNeighbours)(reversedGraph, List(vertex), visitedAcc, visitedAcc, List()).toSet 
     (visitedAcC++ connectedComponent, connectedComponent :: connectedComponentsAcc) 
    }._2.filterNot(_.isEmpty) 
    } 

    def reverse[Vertex](graph: Graph[Vertex]) = { 
    val reverseList = for { 
     (vertex, neighbours) <- graph.toList 
     neighbour <- neighbours 
    } yield (neighbour, vertex) 

    reverseList.groupBy(_._1).mapValues(_.map(_._2).toSet) 
    } 

    private sealed trait NeighboursFunc { 
    def apply[Vertex](graph: Graph[Vertex], vertex: Vertex, entered: Set[Vertex], exited: Set[Vertex]):Set[Vertex] 
    } 

    private object DfsNeighbours extends NeighboursFunc { 
    def apply[Vertex](graph: Graph[Vertex], vertex: Vertex, entered: Set[Vertex], exited: Set[Vertex]) = 
     graph.getOrElse(vertex, Set()).filterNot(entered) 
    } 

    private object TopologicalSortNeighbours extends NeighboursFunc { 
    def apply[Vertex](graph: Graph[Vertex], vertex: Vertex, entered: Set[Vertex], exited: Set[Vertex]) = { 
     val neighbours = graph.getOrElse(vertex, Set()) 
     if(neighbours.exists(neighbour => entered(neighbour) && !exited(neighbour))) 
     throw new IllegalArgumentException("The graph is not a DAG, it contains cycles: " + graph) 
     else 
     neighbours.filterNot(entered) 
    } 
    } 

    @tailrec 
    private def dfsRec[Vertex](neighboursFunc: NeighboursFunc)(graph: Graph[Vertex], toVisit: List[Vertex], 
                  entered: Set[Vertex], exited: Set[Vertex], 
                  exitStack: List[Vertex]): List[Vertex] = { 
    toVisit match { 
     case List() => exitStack 
     case hd :: tl => 
     if(exited(hd)) 
      dfsRec(neighboursFunc)(graph, tl, entered, exited, exitStack) 
     else if(entered(hd) && !exited(hd)) 
      dfsRec(neighboursFunc)(graph, tl, entered, exited + hd, hd :: exitStack) 
     else { // not entered yet 
      dfsRec(neighboursFunc)(graph, neighboursFunc(graph, hd, entered, exited) ++: toVisit, entered + hd, exited, exitStack) 
     } 
    } 
    } 

    @tailrec 
    private def graphDfsRec[Vertex](neighboursFunc: NeighboursFunc)(graph: Graph[Vertex], notVisited: Set[Vertex], 
                    visited: Set[Vertex], order: List[Vertex]): List[Vertex] = { 
    if(notVisited.isEmpty) 
     order 
    else { 
     val orderSuffix = dfsRec(neighboursFunc)(graph, List(notVisited.head), visited, visited, List()) 
     graphDfsRec(neighboursFunc)(graph, notVisited -- orderSuffix, visited ++ orderSuffix, orderSuffix ::: order) 
    } 
    } 
} 

object DirectedGraphTraversalsExamples extends App { 
    import DirectedGraphTraversals._ 

    val graph = Map(
    "B" -> Set("D", "C"), 
    "A" -> Set("B", "D"), 
    "D" -> Set("E"), 
    "E" -> Set("C")) 

    //println(dfs(graph, "A")) 
    println("dfs A " + dfs(graph, "A")) 
    println("dfs B " + dfs(graph, "B")) 

    println("topologicalSort " + topologicalSort(graph)) 
    println("dfs B " + dfs(graph, "B")) 

    println("reverse " + reverse(graph)) 
    println("stronglyConnectedComponents graph " + stronglyConnectedComponents(graph)) 

    val graph2 = graph + ("C" -> Set("D")) 
    println("stronglyConnectedComponents graph2 " + stronglyConnectedComponents(graph2)) 
    println("topologicalSort graph2 " + Try(topologicalSort(graph2))) 
}