4
\$\begingroup\$

I wrote a function in Scala to find out and return a loopy path in a directed graph.

One of the arguments is a graph presented in an adjacent list, and the other is a start node. It returns a pair including a loopy path by a list of nodes.

I wonder if there are more elegant ways of doing this.

  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())
  }

I felt I had to use the indexWhere in this situation, but I suppose it would have other ways to do that.

\$\endgroup\$
1
\$\begingroup\$

You should use an array to check if you have already visited a node and not visits.contains(node), it would give you the answer in constant time instead of linear time.

The overall complexity of your algorithm is exponential. For instance, if you run your algorithm on this graph:

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

where there are n nodes and there are edges from i to j iff i<j then the node i will be explored 2^i times.

Again you can solve this problem using an array (one array for all nodes) to ensure that each node is explored at most one time.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.