Depth-First Search, commonly known as DFS, is a fundamental graph traversal algorithm. It explores a graph by going as deep as possible along each branch before backtracking. DFS is widely used in areas like pathfinding, cycle detection, solving puzzles, and exploring networks. Understanding DFS helps beginners grasp the basic concepts of recursion, graph representation, and traversal strategies, which are key skills in programming.
with hands-on learning.
get the skills and confidence to land your next move.
In Scala, DFS can be implemented using recursion or an explicit stack. Practicing DFS provides insight into how algorithms navigate complex structures like trees and graphs. It also teaches how to handle visited nodes, manage recursion depth, and solve practical problems efficiently.
Program 1: DFS Using Recursion on an Adjacency List
This program demonstrates the classic recursive DFS approach on a simple graph represented with an adjacency list.
object DFSRecursive {
def dfs(node: Int, graph: Map[Int, List[Int]], visited: scala.collection.mutable.Set[Int]): Unit = {
visited += node
println(node)
for (neighbor <- graph.getOrElse(node, Nil)) {
if (!visited.contains(neighbor)) dfs(neighbor, graph, visited)
}
}
def main(args: Array[String]): Unit = {
val graph = Map(
0 -> List(1, 2),
1 -> List(0, 3, 4),
2 -> List(0, 5),
3 -> List(1),
4 -> List(1, 5),
5 -> List(2, 4)
)
val visited = scala.collection.mutable.Set[Int]()
println("DFS traversal starting from node 0:")
dfs(0, graph, visited)
}
}This recursive DFS explores nodes deeply before backtracking. Beginners learn how to manage visited nodes and understand the depth-first traversal order.
Program 2: DFS Using an Explicit Stack
Instead of recursion, this program implements DFS using a stack to track nodes to visit.
object DFSStack {
def dfsStack(start: Int, graph: Map[Int, List[Int]]): Unit = {
val visited = scala.collection.mutable.Set[Int]()
val stack = scala.collection.mutable.Stack[Int]()
stack.push(start)
while (stack.nonEmpty) {
val node = stack.pop()
if (!visited.contains(node)) {
println(node)
visited += node
for (neighbor <- graph.getOrElse(node, Nil).reverse) {
if (!visited.contains(neighbor)) stack.push(neighbor)
}
}
}
}
def main(args: Array[String]): Unit = {
val graph = Map(
0 -> List(1, 2),
1 -> List(0, 3, 4),
2 -> List(0, 5),
3 -> List(1),
4 -> List(1, 5),
5 -> List(2, 4)
)
println("DFS traversal using stack starting from node 0:")
dfsStack(0, graph)
}
}Using a stack avoids recursion and gives beginners a clear view of how DFS manually manages the nodes to explore. This approach is helpful when recursion depth might be too large.
Program 3: DFS on a Graph with String Nodes
This program shows that DFS works not just with integers but also with string-labeled nodes.
object DFSStringNodes {
def dfs(node: String, graph: Map[String, List[String]], visited: scala.collection.mutable.Set[String]): Unit = {
visited += node
println(node)
for (neighbor <- graph.getOrElse(node, Nil)) {
if (!visited.contains(neighbor)) dfs(neighbor, graph, visited)
}
}
def main(args: Array[String]): Unit = {
val graph = Map(
"A" -> List("B", "C"),
"B" -> List("A", "D", "E"),
"C" -> List("A", "F"),
"D" -> List("B"),
"E" -> List("B", "F"),
"F" -> List("C", "E")
)
val visited = scala.collection.mutable.Set[String]()
println("DFS traversal starting from node A:")
dfs("A", graph, visited)
}
}This example demonstrates DFS on non-integer nodes. Beginners learn how flexible DFS is and how to adapt the algorithm to different types of data.
Program 4: DFS for Detecting Cycles in a Graph
DFS can also be used to detect cycles in a graph. This program shows how to identify cycles during traversal.
object DFSDetectCycle {
def dfs(node: Int, parent: Int, graph: Map[Int, List[Int]], visited: scala.collection.mutable.Set[Int]): Boolean = {
visited += node
for (neighbor <- graph.getOrElse(node, Nil)) {
if (!visited.contains(neighbor)) {
if (dfs(neighbor, node, graph, visited)) return true
} else if (neighbor != parent) return true
}
false
}
def main(args: Array[String]): Unit = {
val graph = Map(
0 -> List(1, 2),
1 -> List(0, 3),
2 -> List(0, 3),
3 -> List(1, 2)
)
val visited = scala.collection.mutable.Set[Int]()
val hasCycle = dfs(0, -1, graph, visited)
if (hasCycle) println("Graph contains a cycle")
else println("Graph does not contain a cycle")
}
}This program teaches beginners how DFS can be applied beyond traversal, such as detecting cycles, which is critical in many applications like networking or scheduling.
Program 5: DFS on a Grid (2D Matrix)
DFS is often used to explore grids, like in maze solving or island counting problems.
object DFSGrid {
def dfs(grid: Array[Array[Int]], i: Int, j: Int, visited: Array[Array[Boolean]]): Unit = {
if (i < 0 || j < 0 || i >= grid.length || j >= grid(0).length) return
if (grid(i)(j) == 0 || visited(i)(j)) return
visited(i)(j) = true
println(s"Visited cell ($i, $j)")
dfs(grid, i + 1, j, visited)
dfs(grid, i - 1, j, visited)
dfs(grid, i, j + 1, visited)
dfs(grid, i, j - 1, visited)
}
def main(args: Array[String]): Unit = {
val grid = Array(
Array(1, 1, 0),
Array(0, 1, 1),
Array(1, 0, 1)
)
val visited = Array.ofDim[Boolean](grid.length, grid(0).length)
println("DFS traversal on grid starting from cell (0,0):")
dfs(grid, 0, 0, visited)
}
}This shows how DFS can explore 2D structures. Beginners learn that DFS is not limited to graphs; it works in grids, mazes, and other connected structures.
Frequently Asked Questions (FAQ)
This section answers common beginner questions about Depth-First Search in Scala.
Q1: What is DFS used for?
DFS is used for graph traversal, pathfinding, cycle detection, and exploring connected structures like grids.
Q2: Can DFS handle both directed and undirected graphs?
Yes, DFS works on both types, but cycle detection logic differs slightly.
Q3: Is DFS faster than BFS?
DFS and BFS have similar time complexity, but DFS uses less memory for deep graphs without many branches.
Q4: Can DFS be implemented without recursion?
Yes, using an explicit stack to track nodes, which is helpful when recursion depth is limited.
Q5: How does DFS handle visited nodes?
DFS keeps a set of visited nodes to avoid revisiting and prevent infinite loops in cyclic graphs.
Conclusion
Depth-First Search is a versatile and essential algorithm for graph and grid exploration. In Scala, beginners can implement DFS using recursion or an explicit stack, and adapt it for integers, strings, cycles, or grids. Practicing DFS enhances understanding of recursion, graph traversal, and problem-solving. Exploring different DFS implementations gives confidence to tackle more advanced graph algorithms in the future.
