Scala 中的邻接列表路径

Question

如果我有一个邻接表，在 Scala 中表示如下：

val l = List(
    List((1, 1), (2, 3), (4, 10)),
    List((2, 1)),
    List((3, 1), (4, 5)),
    List(4, 1)),
    List())

每个 "List" 包含有向图中从一个节点到另一个节点的路径成本。所以第一个有3个条目的"List"代表第一个节点的后继者（从0开始计数）。这意味着节点 0 指向节点 1 的成本为 1，节点 2 的成本为 3，节点 4 的成本为 10，依此类推。

如果存在从给定节点到另一个节点的成本最大的路径，如何进行递归计算？我想到了这样的事情：

def hasMaxCostPath: (List[List[(Int, Int)]], Int, Int, Int) => Int => Boolean = (adj, from, to, max) => len =>

所以函数接收邻接表"adj"、起始节点"from"、结束节点"to"、路径的最大成本"max"和最大路径的长度 "len"。所以我认为根据上面给定的邻接表，结果应该如下所示：

hasMaxCostPath(l, 0, 2, 2)(1) == false
hasMaxCostPath(l, 0, 2, 3)(1) == true

此外，如何在给定的最大长度内递归计算从一个指定节点到另一个指定节点的路径的所有成本列表？可能是这样的：

def getPaths: (List[List[(Int, Int)]], List[(Int, Int)], Int, Int) => List[Int] =
(adj, vn, dest, len) =>

所以这个函数会得到邻接表"adj"，一个已经访问过的节点列表"vn" with (node, cost)，其中我们将给定的节点作为起始节点，目标节点 "dest" 和路径的最大长度 "len"。对于此函数，结果可能如下所示：

getPaths(l, List((0, 0)), 2, 1) == List(3)     // Node0 -> Node2
getPaths(l, List((0, 0)), 2, 2) == List(2, 3)  // Node0 -> Node1 -> Node2 AND Node0 -> Node2

抱歉，我是 Scala 的新手

Answer 1

这对你有用吗？

package foo

object Foo {

  def main(args: Array[String]): Unit = {
    val edges = List(
      List((1, 1), (2, 3), (4, 10)),
      List((2, 1)),
      List((3, 1), (4, 5)),
      List((4, 1)),
      List())
    println(hasMaxCostPath(edges,0,1,2))
    println(hasMaxCostPath(edges,0,2,2))
  }

  def hasMaxCostPath(edges: List[List[(Int, Int)]], start: Int, end: Int, maxCost: Int): Boolean = {
    maxCost > 0 &&
    edges(start).exists(a =>
      (a._1 == end && a._2 <= maxCost) ||
      hasMaxCostPath(edges, a._1, end, maxCost - a._2)
    )
  }

}

编辑：====

上述解决方案没有考虑长度参数。这是一个带有长度参数的解决方案：

package foo

object Foo {

  def main(args: Array[String]): Unit = {
    val edges = List(
      List((1, 1), (2, 3), (4, 10)),
      List((2, 1)),
      List((3, 1), (4, 5)),
      List((4, 1)),
      List())
      assert(! hasMaxCostPath(edges,0,4,4,3))
      assert(hasMaxCostPath(edges,0,4,4,4))
  }

  def hasMaxCostPath(edges: List[List[(Int, Int)]], start: Int, end: Int, maxCost: Int, maxLength: Int): Boolean = {
    maxLength > 0 &&
    maxCost >= 0 &&
    edges(start).exists(a =>
      (a._1 == end && a._2 <= maxCost) ||
      hasMaxCostPath(edges, a._1, end, maxCost - a._2, maxLength - 1)
    )
  }

}

=== 编辑：

这是一个解决方案，包括您的第二个问题：

package foo

object Foo {

  def main(args: Array[String]): Unit = {
    val edges = List(
      List((1, 1), (2, 3), (4, 10)),
      List((2, 1)),
      List((3, 1), (4, 5)),
      List((4, 1)),
      List())
    assert(! hasMaxCostPath(edges,0,4,4,3))
    assert(hasMaxCostPath(edges,0,4,4,4))
    assert(getMaxCostPaths(edges,0,0,5,5) == List())
    assert(getMaxCostPaths(edges,0,1,1,1) == List(List(0,1)))
    assert(getMaxCostPaths(edges,0,2,2,2) == List(List(0,1,2)))
    assert(getMaxCostPaths(edges,0,2,5,5) == List(List(0,2), List(0,1,2)))
  }

  def hasMaxCostPath(edges: List[List[(Int, Int)]], start: Int, end: Int, maxCost: Int, maxLength: Int): Boolean = {
    maxLength > 0 &&
    maxCost >= 0 &&
    edges(start).exists(a =>
      (a._1 == end && a._2 <= maxCost) ||
      hasMaxCostPath(edges, a._1, end, maxCost - a._2, maxLength - 1)
    )
  }

  def getMaxCostPaths(
         edges: List[List[(Int, Int)]],
         from: Int, to: Int,
         maxCost: Int,
         maxLength: Int): List[List[Int]] = {
      getMaxCostPathsRec(edges, from, to, maxCost, maxLength, List(from))
  }

  def getMaxCostPathsRec(
         edges: List[List[(Int, Int)]],
         start: Int, end: Int,
         maxCost: Int,
         maxLength: Int,
         path: List[Int]) : List[List[Int]] = {
    if (maxLength <= 0 || maxCost < 0) return List()
    val direct = edges(start).filter(a => a._1 == end && a._2 <= maxCost).map(edge => path ::: List(edge._1))
    val transitive = edges(start).flatMap(a =>
      getMaxCostPathsRec(edges, a._1, end, maxCost - a._2, maxLength - 1, path ::: List(a._1))
    )
    direct ::: transitive
  }

}

Scala 中的邻接列表路径

Adjacency-List Paths in Scala

algorithm

scala

directed-graph

path-finding

adjacency-list