Depth First Order Algorithm

Depth First Order Algorithm is a graph traversal technique that explores as far as possible along a branch before backtracking. It is one of the core algorithms used in graph theory, and is particularly useful in solving problems related to connectivity, path-finding, and network flow. This algorithm can be implemented using recursion or an explicit stack data structure, and it can be applied to both directed and undirected graphs. The basic idea behind the depth-first search is to visit a vertex, mark it as visited, visit all its unvisited neighbors in a similar manner, and then backtrack to explore other vertices. The Depth First Order Algorithm is often used to generate a topological sort of the vertices in a directed acyclic graph (DAG), which is a linear ordering of the vertices such that for every directed edge (u, v), vertex u comes before vertex v in the ordering. This linear ordering is useful in scheduling tasks with dependencies, detecting cycles in graphs, and solving other graph-related problems. The depth-first search algorithm is also used to find the strongly connected components of a directed graph, which are maximal subgraphs where every vertex is reachable from every other vertex. Overall, the Depth First Order Algorithm is an essential tool in graph theory and computer science, with numerous important applications.
package org.gs.digraph

/** Find pre-order, post-order, & reverse post-order of digraph using depth first search
  *
  * @constructor creates a new DepthFirstOrder with a digraph and its number of vertices
  * @param g 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.
  */
class DepthFirstOrder(g: Digraph ) extends BaseDepthFirstOrder(g.numV) {

  protected def dfs(v: Int): Unit = {
    marked(v) = true
    preCounter += 1
    _pre(v) = preCounter
    preOrder.enqueue(v)
    g.adj(v) foreach (x => if (!marked(x)) dfs(x))
    postOrder.enqueue(v)
    postCounter += 1
    _post(v) = postCounter
  }
}

LANGUAGE:

DARK MODE: