Directed DFS Algorithm
The Directed Depth-First Search (DFS) Algorithm is a graph traversal technique used to explore all the vertices and edges of a directed graph in a depthward motion. It is particularly useful for solving problems related to connectivity, pathfinding, and cycle detection in directed graphs. The algorithm starts from a source vertex and traverses as deep as possible along each branch before backtracking. The algorithm typically uses a stack data structure to keep track of unexplored vertices, and a visited set to mark the vertices that have already been explored.
In the Directed DFS Algorithm, the traversal begins by marking the starting vertex as visited and pushing it onto the stack. Then, the algorithm iteratively explores the adjacent vertices of the current vertex. If an adjacent vertex has not been visited, it is marked as visited, and the algorithm pushes it onto the stack before moving on to its neighbors. If all adjacent vertices of the current vertex have been visited, the algorithm backtracks by popping the stack and moving back to the previously visited vertex. This process continues until the stack is empty, which signifies that all reachable vertices have been visited. If the graph is not connected, the algorithm can be executed multiple times with different starting vertices to explore all the connected components of the graph.
package org.gs.digraph
/** Find reachable vertices from single or multiple source vertices
*
* @constructor creates a new DirectedDFS with a digraph and any number of source vertices
* @param g Digraph
* @param sources a variable number of vertices
* @see [[https://algs4.cs.princeton.edu/42directed/DirectedDFS.java.html]]
* @author Scala translation by Gary Struthers from Java by Robert Sedgewick and Kevin Wayne.
*/
class DirectedDFS(g: Digraph, sources: Int*) {
val marked = new Array[Boolean](g.numV)
private var _count = 0
/** returns number of vertices reachable from s */
def count(): Int = _count
private def dfs(v: Int): Unit = {
_count += 1
marked(v) = true
g.adj(v) foreach (w => if (!marked(w)) dfs(w))
}
sources foreach (v => if(!marked(v)) dfs(v))
/** returns if there is a path from any source to v */
def isMarked(v: Int): Boolean = marked(v)
}
