純函數圖連接

Question

我試圖更好地理解函數式編程，並決定實現一些經典的圖算法。我已經通過將BFS循環封裝到尾遞歸函數中來實現連接，但此代碼看起來並不比命令式好得多。有沒有更好的實現它的方法（使用for解析，單子，不管）？

object Graph { 
    def apply(n: Int) = new Graph(n, Vector.fill(n)(List.empty[Int])) 
} 

class Graph private (val n: Int, val adj: IndexedSeq[List[Int]]) { 
    def addEdge(u: Int, v: Int) = { 
    new Graph(n, adj.updated(u, v :: adj(u)).updated(v, u :: adj(v))) 
    } 


    def connected = { 
    @tailrec 
    def connectedIter(q: Queue[Int], visited: Seq[Boolean]) : Boolean = { 
     if(q.isEmpty) visited.forall(x => x) else { 
     val (v, newq) = q.dequeue 
     val newVisited = visited.updated(v, true) 
     connectedIter(adj(v).foldLeft(newq){(acc, x) => if(visited(x)) acc else acc.enqueue(x)}, newVisited) 
     } 
    } 

    connectedIter(Queue[Int](0), IndexedSeq.fill(n)(false)) 
    } 
} 

P.S.它看起來具有固有的遞歸DFS

def reachableDfs(v: Int): Seq[Boolean] = reachableDfs(v, Vector.fill(n)(false)) 

    private def reachableDfs(v: Int, visited: Seq[Boolean]) : Seq[Boolean] = { 
    val newV = visited.updated(v, true) 
    adj(v).filterNot{x => newV(x)}.foldLeft(newV){(acc, x) => reachableDfs(x, acc)} 
    } 

Answer 1

你總是可以嘗試另一種更實用的方法來圖表數據類型：

Martin Erwig。 2001.歸納圖和函數圖算法。 J. Funct。程序。 11，5（2001年9月），467-492。 DOI = 10.1017/S0956796801004075

Answer 2

您可以用Set行動表達這個好一點，雖然這可能是效率較低：

object Graph { 
    def apply(n: Int) = new Graph(n, Vector.fill(n)(Set.empty)) 
} 

class Graph private (val n: Int, val adj: IndexedSeq[Set[Int]]) { 
    def addEdge(u: Int, v: Int) = { 
    new Graph(n, adj.updated(u, adj(u) + v).updated(v, adj(v) + u)) 
    } 

def connected = { 
    @tailrec 
    def connectedIter(q: Queue[Int], visited: Set[Int]): Boolean = { 
    if (q.isEmpty) visited.size == n else { 
     val (v, newq) = q.dequeue 
     connectedIter(newq enqueue (adj(v) -- visited), visited ++ adj(v)) 
    } 
    } 

connectedIter(Queue(0), Set.empty) 
} 
}