2

我在 Scala 中编写了一个函数来找出并返回有向图中的循环路径。程序如下，其中一个参数是相邻列表中呈现的图形，另一个是起始节点。它通过节点列表返回一对，包括循环路径。

我想知道有更优雅的方法可以做到这一点。如果您愿意，请分享您的想法。谢谢。

  def GetACycle(start: String, maps: Map[String, List[String]]): (Boolean, List[String]) = {
    def explore(node: String, visits: List[String]): (Boolean, List[String]) = {
      if (visits.contains(node)) (true, (visits.+:(node)).reverse)
      else {
        if (maps(node).isEmpty) (false, List())
        else {
          val id = maps(node).indexWhere(x => explore(x, visits.+:(node))._1)
          if (id.!=(-1))
            explore(maps(node)(id), visits.+:(node))
          else
            (false, List())
        }
      }
    }
    explore(start, List())
  }

我觉得在这种情况下我必须使用 indexWhere，但我想它还有其他方法可以做到这一点。

4

1 回答 1

1

您应该使用数组来检查您是否已经访问过一个节点而不是visits.contains(node)，它会以恒定时间而不是线性时间为您提供答案。

你的算法的整体复杂性是指数级的。例如，如果您在此图上运行算法：

0 -> 1, 2, ..., n
1 -> 2, ..., n
...

如果有n节点并且有从i到jiff的边，i<j那么该节点i将被探索2^i次数。

同样，您可以使用一个数组（所有节点一个数组）来解决这个问题，以确保每个节点最多被探索一次。

于 2012-12-10T10:46:54.313 回答