When working with data structures like graphs or trees, one of the most common tasks is searching through nodes to find a specific value or traverse all elements. One powerful technique for this is Depth-First Search (DFS). DFS is an algorithm that explores as far as possible along each branch before backtracking. It dives deep into the structure, making it especially useful for problems where you need to explore all possibilities or paths, such as solving mazes, analyzing networks, or checking for connectivity in graphs.
with hands-on learning.
get the skills and confidence to land your next move.
DFS is widely used in computer science and programming because it helps in understanding relationships between nodes, detecting cycles, and solving problems like pathfinding. Learning DFS in Kotlin is a great way for beginners to understand recursive and iterative problem-solving techniques. Implementing DFS strengthens the understanding of graphs, recursion, and stacks, all of which are essential for efficient programming.
Program 1: DFS Using Recursion on a Graph
This program shows a classic recursive DFS on a graph represented using an adjacency list.
fun dfsRecursive(graph: Map<Int, List<Int>>, start: Int, visited: MutableSet<Int>) {
if (visited.contains(start)) return
println(start)
visited.add(start)
for (neighbor in graph[start] ?: emptyList()) {
dfsRecursive(graph, neighbor, visited)
}
}
fun main() {
val graph = mapOf(
0 to listOf(1, 2),
1 to listOf(0, 3, 4),
2 to listOf(0, 4),
3 to listOf(1, 5),
4 to listOf(1, 2, 5),
5 to listOf(3, 4)
)
println("DFS Traversal starting from node 0:")
dfsRecursive(graph, 0, mutableSetOf())
}In this program, the function calls itself for every neighbor that hasn’t been visited yet. Beginners can see how recursion naturally mirrors the structure of a graph, diving deep into nodes and backtracking automatically when no new nodes are left.
Program 2: DFS Using Stack (Iterative Approach)
Sometimes recursion is not preferred due to stack limitations, so DFS can also be implemented iteratively using a stack.
fun dfsIterative(graph: Map<Int, List<Int>>, start: Int) {
val visited = mutableSetOf<Int>()
val stack = mutableListOf(start)
while (stack.isNotEmpty()) {
val node = stack.removeAt(stack.size - 1)
if (!visited.contains(node)) {
println(node)
visited.add(node)
stack.addAll(graph[node] ?: emptyList())
}
}
}
fun main() {
val graph = mapOf(
0 to listOf(1, 2),
1 to listOf(0, 3, 4),
2 to listOf(0, 4),
3 to listOf(1, 5),
4 to listOf(1, 2, 5),
5 to listOf(3, 4)
)
println("DFS Iterative Traversal starting from node 0:")
dfsIterative(graph, 0)
}This iterative approach mimics recursion using a stack. Beginners can understand how data structures like stack are used to control traversal order and avoid recursion limits.
Program 3: DFS on a Binary Tree
DFS can also be applied to trees. Here’s an example of recursive DFS on a binary tree.
data class TreeNode(val value: Int, val left: TreeNode? = null, val right: TreeNode? = null)
fun dfsBinaryTree(node: TreeNode?) {
if (node == null) return
println(node.value)
dfsBinaryTree(node.left)
dfsBinaryTree(node.right)
}
fun main() {
val tree = TreeNode(1,
TreeNode(2, TreeNode(4), TreeNode(5)),
TreeNode(3, TreeNode(6), TreeNode(7))
)
println("DFS Traversal of Binary Tree:")
dfsBinaryTree(tree)
}This program demonstrates pre-order traversal, which is a form of DFS. Beginners can see how recursive calls naturally process the left and right subtrees before backtracking.
Program 4: DFS to Detect Cycle in a Graph
DFS can also be used for problem-solving, such as detecting cycles in a graph.
fun hasCycle(graph: Map<Int, List<Int>>, node: Int, visited: MutableSet<Int>, parent: Int): Boolean {
visited.add(node)
for (neighbor in graph[node] ?: emptyList()) {
if (!visited.contains(neighbor)) {
if (hasCycle(graph, neighbor, visited, node)) return true
} else if (neighbor != parent) {
return true
}
}
return false
}
fun main() {
val graph = mapOf(
0 to listOf(1, 2),
1 to listOf(0, 3),
2 to listOf(0, 3),
3 to listOf(1, 2)
)
val visited = mutableSetOf<Int>()
val hasCycle = hasCycle(graph, 0, visited, -1)
println("Graph has cycle: $hasCycle")
}Here, DFS helps in checking whether revisiting a node forms a loop. Beginners can see practical applications of DFS beyond simple traversal.
Program 5: DFS on a Grid (Maze Traversal)
DFS is also useful in grid-based problems like mazes or pathfinding.
fun dfsGrid(grid: Array<IntArray>, x: Int, y: Int, visited: Array<BooleanArray>) {
if (x < 0 || y < 0 || x >= grid.size || y >= grid[0].size || visited[x][y] || grid[x][y] == 0) return
println("Visiting: ($x, $y)")
visited[x][y] = true
dfsGrid(grid, x + 1, y, visited)
dfsGrid(grid, x - 1, y, visited)
dfsGrid(grid, x, y + 1, visited)
dfsGrid(grid, x, y - 1, visited)
}
fun main() {
val grid = arrayOf(
intArrayOf(1, 1, 0, 0),
intArrayOf(1, 1, 0, 1),
intArrayOf(0, 0, 1, 1),
intArrayOf(0, 1, 1, 0)
)
val visited = Array(grid.size) { BooleanArray(grid[0].size) }
println("DFS Traversal on Grid:")
dfsGrid(grid, 0, 0, visited)
}This example shows DFS exploring a 2D maze, visiting all connected cells. Beginners can understand how DFS can be adapted to multi-dimensional structures.
Frequently Asked Questions (FAQ)
Q1: What is Depth-First Search (DFS)?
DFS is a graph traversal algorithm that explores as far as possible along each branch before backtracking.
Q2: When should I use DFS?
DFS is useful for exploring all nodes, detecting cycles, solving mazes, and checking connectivity in graphs.
Q3: Can DFS be implemented iteratively?
Yes, using a stack, DFS can be implemented without recursion to avoid stack overflow.
Q4: What is the time complexity of DFS?
The time complexity is O(V + E) for a graph, where V is the number of vertices and E is the number of edges.
Q5: How does DFS differ from BFS?
DFS explores deep along a branch before backtracking, while BFS explores all neighbors level by level.
Conclusion
Depth-First Search is a fundamental algorithm for exploring graphs, trees, and grids. In Kotlin, it can be implemented both recursively and iteratively, providing flexibility for different applications. By practicing DFS, beginners can understand recursion, stacks, and traversal strategies while gaining insight into problem-solving in structured data. Mastering DFS opens doors to more advanced graph algorithms and real-world applications like pathfinding and network analysis.
