Implementing Basic Graph Algorithms in Scala

Graph theory is a fundamental concept in computer science, with applications ranging from social networks to mapping and logistics. In this post, we'll explore how to implement some basic graph algorithms in Scala, a powerful and expressive language that's well-suited for this task.

Representing a Graph

Before we dive into algorithms, we need a way to represent a graph. A common and efficient way to do this is using an adjacency list. We can represent the graph as a map where the keys are the nodes (or vertices) and the values are lists of their adjacent nodes.

Here's a simple case class for a generic graph:

case class Graph[T](adjacencyList: Map[T, List[T]]) {
  def neighbors(node: T): List[T] = adjacencyList.getOrElse(node, Nil)
}

This representation is flexible and allows us to work with different types of nodes (e.g., Int, String, etc.).

Breadth-First Search (BFS)

Breadth-First Search is an algorithm for traversing or searching a graph. It explores the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

Here is a possible implementation in Scala:

import scala.collection.mutable
 
def bfs[T](graph: Graph[T], startNode: T): List[T] = {
  val queue = mutable.Queue[T](startNode)
  val visited = mutable.Set[T](startNode)
  val result = mutable.ListBuffer[T]()
 
  while (queue.nonEmpty) {
    val node = queue.dequeue()
    result += node
 
    for (neighbor <- graph.neighbors(node)) {
      if (!visited.contains(neighbor)) {
        visited += neighbor
        queue.enqueue(neighbor)
      }
    }
  }
  result.toList
}

This implementation uses a queue to keep track of the nodes to visit and a set to store the visited nodes to avoid cycles.

Depth-First Search (DFS)

Depth-First Search is another graph traversal algorithm. It explores as far as possible along each branch before backtracking.

Here is a recursive implementation of DFS in Scala:

def dfs[T](graph: Graph[T], startNode: T): List[T] = {
  val visited = mutable.Set[T]()
  val result = mutable.ListBuffer[T]()
 
  def dfsRecursive(node: T): Unit = {
    visited += node
    result += node
 
    for (neighbor <- graph.neighbors(node)) {
      if (!visited.contains(neighbor)) {
        dfsRecursive(neighbor)
      }
    }
  }
 
  dfsRecursive(startNode)
  result.toList
}

This version uses the call stack for recursion to explore each branch of the graph.

Conclusion

In this post, we've seen how to represent a graph and implement two fundamental traversal algorithms, BFS and DFS, in Scala. These algorithms are the building blocks for solving many other graph-related problems. Scala's powerful features, like case classes and its rich collections library, make it a great choice for implementing these complex data structures and algorithms.