难以以功能方式维护图形算法中数据结构的完整性

Question

我正在尝试解决来自 UVA 在线判断网站的问题，特别是 539 我需要使用 DFS 来查找最长路径的问题，我可以强制解决它，但我想使用 scala 以更实用的惯用方式进行操作，问题是当来自分支的算法 return 时，数据结构不会更新以供其他分支使用，不想使用 vars，也不想使用副作用，这是我的代码：

type Vertex=Int

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

def DFS(start: Vertex, g: Graph): Int = {

  def loop(v: Vertex, visited: List[Vertex], size: Int = 0): Int = {

  val neighbours: List[Vertex] = ( g(v) filterNot visited.contains ).toList
   if (neighbours == Nil) size
   else {
  ( for (elem <- neighbours) yield loop(elem, v :: visited, size + 1) ).max }
    }
loop(start, List())
}

Answer 1

您需要存储路径，而不是访问集合中的顶点（比 List in contains 操作性能更好）。你也应该从所有顶点开始尝试这个。检查这个：

type Vertex = Int

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

def DFS(g: Graph): Int = {

  def loop(current: Vertex, visited: Set[(Vertex, Vertex)]): Int = {
    val neighbours = g(current).filterNot(contains(visited, current, _))
    if (neighbours.isEmpty)
      visited.size
    else {
      (for {
        elem <- g(current).filterNot(contains(visited, current, _))
      } yield (loop(elem, add(visited, current, elem)))).max
    }
  }

  (for {
    elem <- g.keys
  } yield (loop(elem, Set()))).max
}

def add(set:Set[(Vertex,Vertex)], v1:Vertex, v2:Vertex): Set[(Vertex,Vertex)] =
  if(v1 < v2) add(set, v2,v1) else set.+((v1,v2))
def contains(set:Set[(Vertex,Vertex)], v1:Vertex, v2:Vertex):Boolean =
  if(v1 < v2) contains(set, v2,v1) else set.contains((v1,v2))

难以以功能方式维护图形算法中数据结构的完整性

trouble maintaining the integrity of the data structure in a graph algorithm in a functional way

algorithm

functional-programming

scala

depth-first-search

data-structures