2

有向グラフのループ パスを見つけて返す関数を Scala で作成しました。プログラムは次のとおりで、引数の 1 つは隣接するリストに表示されるグラフであり、もう 1 つは開始ノードです。ノードのリストでループパスを含むペアを返します。

もっとエレガントな方法があるのだろうか。もしよろしければ、あなたの考えを共有してください。ありがとう。

  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エッジがある場合、ノードは回探索されます。iji<ji2^i

ここでも、配列 (すべてのノードに対して 1 つの配列) を使用してこの問題を解決し、各ノードが最大 1 回探索されるようにすることができます。

于 2012-12-10T10:46:54.313 に答える