0

我有以下带有目标节点“E”的地图：

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

它描述了一个有向节点图，如下所示：

  
  一个
 / \
 公元前
   / \     
  德

我需要在任何时候输入图表并生成到目标节点的路线。

Example 1: Enter at A -> Route: A->C->E
Example 2: Enter at D -> Route: D->C->E
Example 3: Enter at B -> Route: B->A->C->E

有谁知道一个紧凑的算法可以做到这一点，因为这之前必须尝试过。

期待您的来信。

干杯，

杰兹

4

2 回答 2

2

所以，这里是：

  val map = List("A" -> "B", "A" -> "C", "C" -> "D", "C" -> "E")

  def pathOf(tree: Iterable[(String,String)],from: String,to: String, path: List[String] = Nil): List[String] = {
    if(from == to) return to::path
    tree.filterNot{ case(a,b) => path.contains(a)||path.contains(b) }
    .collect{
      case (a,b) if a == to => b
      case (a,b) if b == to => a
    }.map{ x => pathOf(tree,from,x,to::path) }
    .find{ _.nonEmpty }
    .getOrElse(Nil)
  }

用例：

scala>  pathOf(map,"B","E").mkString("->")
res1: String = B->A->C->E

scala>  pathOf(map,"C","E").mkString("->")
res2: String = C->E
于 2012-11-26T15:41:20.177 回答
1

作为 Scala 的新手，我把这个问题作为对自己的一个很好的练习，并希望与大家分享我的解决方案。欢迎任何意见！

顺便说一句，@Eastsun 给出的解决方案是深度优先搜索，它“记住”每条路径中的访问节点，而我的是广度优先搜索，不需要记忆（尽管您绝对可以添加此功能以提高效率）。对于树，它们产生相同的答案，但对于一般图，它们可能会有所不同。

每个节点的邻居也可以被缓存以进行优化。

val graph = Vector(("A","B"), ("A","C"), ("C","D"), ("C","E"))
def adjacent(a: String) = {
  graph flatMap {
    case (`a`, x) => Some(x)
    case (x, `a`) => Some(x)
    case _ => None
  }
}
def go(from: String, to: String) {
  def expand(paths: Vector[Vector[String]]) {
    paths.find(_.last==to) match {
      case Some(x) => println(x); return
      case None => expand(paths flatMap { e => 
        adjacent(e.last) map (e :+ _) 
      })
    }
  }
  expand(Vector(Vector(from)))
}
// tests
go("A","E")  // Vector(A, C, E)
go("B","E")  // Vector(B, A, C, E)
go("D","E")  // Vector(D, C, E)

带记忆的版本：更改

adjacent(e.last) map (e :+ _)

至

adjacent(e.last) filterNot (x => paths.flatten contains x) map (e :+ _)

或将此功能放在相邻的功能中。

于 2012-11-27T16:41:55.953 回答