Base Depth First Order Algorithm

The Base Depth First Order (BDF) Algorithm is a graph traversal algorithm that belongs to the family of depth-first search (DFS) algorithms. It is primarily used for searching through tree or graph data structures, exploring nodes and their branches as far as possible along a particular path before backtracking. In comparison to other traversal algorithms, such as Breadth-First Search (BFS), which visit all neighbors of a node before moving on to their neighbors, BDF prioritizes visiting the descendants of a node before exploring its neighbors. This approach often enables faster discovery of solutions in certain types of problems, such as in constraint satisfaction or game-tree search applications. The BDF algorithm starts at a root node, visiting it and marking it as explored. Then, it recursively explores all unvisited adjacent nodes by following each branch as deep as possible, backtracking only when it encounters a dead-end or a previously visited node. The process continues until all nodes in the graph have been explored or a specific target node has been found. BDF is particularly useful in situations where we have limited information about the graph or when we're looking for the shortest path to a specific node. As the algorithm traverses the graph, it maintains a stack data structure to remember the path it took, enabling efficient backtracking when necessary. Additionally, BDF can be easily adapted for various purposes, such as topological sorting or cycle detection in directed graphs.
package org.gs.digraph

import scala.collection.mutable.Queue

/** Common code for finding pre-order, post-order, & reverse post-order in digraphs
  *
  * @constructor called by subclass with number of vertices
  * @param v number of vertices in digraph
  * @see [[https://algs4.cs.princeton.edu/42directed/DepthFirstOrder.java.html]]
  * @author Scala translation by Gary Struthers from Java by Robert Sedgewick and Kevin Wayne.
  */
abstract class BaseDepthFirstOrder(v: Int) {

  protected val _pre = new Array[Int](v)
  protected val _post = new Array[Int](v)
  protected val preOrder = new Queue[Int]()
  protected val postOrder = new Queue[Int]()
  protected var preCounter = 0
  protected var postCounter = 0
  protected val marked = Array.fill[Boolean](v)(false)
  for {
    i <- 0 until v
    if (!marked(i))
  } dfs(i)

  /** @param v vertex for depth first search to find pre-order & post-order */
  protected def dfs(v: Int): Unit

  /** returns pre-order number of vertex v */
  def pre(v: Int): Int = _pre(v)

  /** returns post-order number of vertex v */
  def post(v: Int): Int = _post(v)

  /** returns vertices in pre-order of vertex v */
  def pre(): List[Int] = preOrder.toList

  /** returns vertices in post-order of vertex v */
  def post(): List[Int] = postOrder.toList

  /** returns vertices in reverse post-order, which is a topological order, of vertex v */
  def reversePost(): List[Int] = postOrder.reverse.toList
}

LANGUAGE:

DARK MODE: