Scala - Use DFS for detecting a cycle? My code is buggy, and I can't seem to figure out why

Question

I am trying to write a function that returns true if the graph has a cycle but I am dreadfully struggling. I represent a graph in Scala as shown below, where the index of each sublist represent a node 0,1,2 onwards, and the components of that sublist indicate an edge from index of sublist to node 2 at cost 1 for example. Note this is a undirected graph representation. Below is an example of a undirected graph that does have a cycle.

ListBuffer(
  ListBuffer((1, 1), (2, 1), (3, 1)),
  ListBuffer((0, 1), (2, 2), (3, 2)),
  ListBuffer((0, 1), (1, 2)),
  ListBuffer((0, 1), (1, 2)))
)

Here is the code I have but it does not work, and I cannot seem to figure out why.

def hasCycle(graph: ListBuffer[ListBuffer[(Int, Int)]]): Boolean = {
  var visited: HashSet[Int] = HashSet()
  var lst: ListBuffer[Int] = ListBuffer()
  for (node <- graph.indices) {
    if (visited.contains(node)) {
      true
    } else {
      visited += node
      for (item <- getChildren(graph, node)) {
        visited += item
        lst += item
      }
      for (i <- lst) {
        visit(graph, i, node)
        lst = ListBuffer()
      }
    }
  }
  def visit(g: ListBuffer[ListBuffer[(Int, Int)]], node: Int, parent: Int): Unit = {
    for (child <- getChildren(g, node)) {
      if (visited.contains(child) && (child != parent)) {
          true
      } else if (!visited.contains(child) && (child != parent)) {
        visit(g, child, child)
      }
    }
  }
  false
 }
 /* Return the adjacent nodes to parent in graph */
 def getChildren(graph:  ListBuffer[ListBuffer[(Int, Int)]], parent: Int): ListBuffer[Int] = {
    var parentToChildren: Map[Int, ListBuffer[Int]] = Map()
    var childrenOfI: ListBuffer[Int] = ListBuffer()
    for (i <- graph.indices) {
      for (j <- graph(i)) {
        childrenOfI += j._1
      }
      parentToChildren += (i -> childrenOfI)
      childrenOfI = ListBuffer()
    }
    parentToChildren(parent)
  }

Answer 1

Here is an approach (admittedly not rigorously tested, so let me know!), sub-optimal but which does contain some Scala idiom (use of find on collection, Set, immutable List...):

type Graph = List[List[(Int, Int)]]

val g: Graph = List(
  List((1, 1), (2, 1)),
  ...
  )

def hasCycle(g: Graph): Boolean = {
  (0 to g.length - 1).find { source => //-- is there a cycle starting at this node?
    pathTo(source, source, (0 to source).toSet)
  }.isDefined
}

def pathTo(source: Int, destination: Int, visited: Set[Int]): Boolean = {
  //-- Is there a path from source to destination excluding visited?
  g(source).find { node => //-- find first case where
    node._1 == destination || ( //-- we've reached destination, or ...
      //-- we're allowed to continue (not yet visited), and there's a path this way
      !visited.contains(node._1) && pathTo(node._1, destination, visited + node._1))
  }.isDefined
}

As an aside, if you haven't seen them, you might also be interested in the answers to How do I check if a Graph is Acyclic