Depth First Search Algorithm

The Depth First Search (DFS) algorithm is a widely used graph traversal technique that explores nodes in a graph as deep as possible before backtracking. It operates on the principle of visiting all the vertices of a graph in a depthward fashion, traversing from the starting node to the farthest node along a particular path and then backtracking to explore other paths. DFS can be implemented using recursion or an explicit stack data structure, and it is commonly used for solving problems such as pathfinding, connectivity, and topological sort in a wide range of applications, including artificial intelligence, network analysis, and game development. The algorithm begins by selecting a source node and marking it as visited. It then recursively visits each unvisited adjacent node from the current node, marking them as visited as the traversal proceeds. Once there are no more unvisited adjacent nodes, the algorithm backtracks to the previous node in the path and continues searching for unvisited nodes until all the nodes in the graph have been explored. DFS is often contrasted with the Breadth First Search (BFS) algorithm, which explores nodes in a breadthward fashion, visiting all neighbors of a node before proceeding to their neighbors. While both algorithms can be used for similar purposes, DFS is more suitable for problems where the solution lies deep in the search space or when the search space is large and not all nodes need to be explored.
package org.gs.graph

/** Depth first search of a graph
  *
  * Mark a vertex as visited then, recursively visit its adjacent vertices that haven't been marked
  *
  * @constructor creates a new DepthFirstSearch with a graph and source vertex
  * @param g Graph
  * @param s source vertex
  * @see [[https://algs4.cs.princeton.edu/41undirected/DepthFirstSearch.java.html]]
  * @author Scala translation by Gary Struthers from Java by Robert Sedgewick and Kevin Wayne.
  */
class DepthFirstSearch(g: Graph, s: Int) {
  val marked = new Array[Boolean](g.numV)
  private var _count = 0

   /** returns number of vertices connected to 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))
  }
  dfs(s)
}

LANGUAGE:

DARK MODE: