Tail recursive graph traversal: https://www.meetup.com/sonoran-scala/events/283741949/

graph.sc

type Graph[A] = Map[A, Set[A]]

def bfs[A](graph: Graph[A], start: A, end: A): Option[List[A]] =
  import scala.collection.immutable.ListSet
  @annotation.tailrec
  def bfsTR(remaining: List[A], visited: ListSet[A]): Option[List[A]] =
    remaining match
      case Nil => None
      case h :: t if visited(h) => bfsTR(t, visited)
      case h :: _ if h == end => Some((visited + h).toList)
      case h :: t => bfsTR(t ++ graph(h).toList, visited + h)
  bfsTR(List(start), ListSet.empty)

// Try to traverse `graph` from `start` to `end`
def search[A](graph: Graph[A], start: A, end: A): Boolean =
  bfs(graph, start, end).isDefined

////////////////////////////////////////////////////////////////////////

def test[A](graph: Graph[A], start: A, end: A): Unit =
  println(s"${start} -> ${end}: ${bfs(graph, start, end)}")

////////////////////////////////////////////////////////////////////////

/*
  A
 / \
B   C
|   |
D   E
  /
F - G
*/
val g: Graph[String] =
  Map(
    "A" -> Set("B", "C"),
    "B" -> Set("D"),
    "C" -> Set("E"),
    "D" -> Set.empty,
    "E" -> Set("F"),
    "F" -> Set("G"),
    "G" -> Set.empty
  )

test(g, "A", "G")
test(g, "B", "D")
test(g, "B", "G")
test(g, "C", "F")

////////////////////////////////////////////////////////////////////////

/*
$ scala-cli --scala 3.1.1 graph.sc
A -> G: Some(List(A, B, C, D, E, F, G))
B -> D: Some(List(B, D))
B -> G: None
C -> F: Some(List(C, E, F))
*/