Chapters

Hide chapters

Data Structures & Algorithms in Kotlin

First Edition · Android 10 · Kotlin 1.3 · IDEA

Before You Begin

Section 0: 3 chapters
Show chapters Hide chapters

21. Depth-First Search
Written by Irina Galata, Kelvin Lau and Vincent Ngo

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

In the previous chapter, you looked at breadth-first search (BFS) in which you had to explore every neighbor of a vertex before going to the next level. In this chapter, you’ll look at depth-first search (DFS), another algorithm for traversing or searching a graph.

There are many applications for DFS:

  • Topological sorting.
  • Detecting a cycle.
  • Pathfinding, such as in maze puzzles.
  • Finding connected components in a sparse graph.

To perform a DFS, you start with a given source vertex and attempt to explore a branch as far as possible until you reach the end. At this point, you’d backtrack (move a step back) and explore the next available branch until you find what you’re looking for or until you’ve visited all the vertices.

DFS example

The example graph below is the same as the previous chapter.

Using the same graph helps you to see the difference between BFS and DFS.

You’ll use a stack to keep track of the levels you move through. The stack’s LIFO approach helps with backtracking. Every push on the stack means that you move one level deeper. When you reach a dead end, you can pop to return to a previous level.

  1. As in the previous chapter, you choose A as a starting vertex and add it to the stack.

  2. As long as the stack is not empty, you visit the top vertex on the stack and push the first neighboring vertex that you haven’t yet visited. In this case, you visit A and push B.

Recall from the previous chapter that the order in which you add edges influences the result of a search. In this case, the first edge added to A was an edge to B, so B is pushed first.

  1. You visit B and push E because you already visited A.

  2. You visit E and push F.

Note that, every time you push on the stack, you advance farther down a branch. Instead of visiting every adjacent vertex, you continue down a path until you reach the end and then backtrack.

  1. You visit F and push G.

  2. You visit G and push C.

  1. The next vertex to visit is C. It has neighbors [A, F, G], but you already visited these. You reached a dead end, so it’s time to backtrack by popping C off the stack.

  2. This brings you back to G. It has neighbors [F, C], but you also already visited these. Another dead end, pop G.

  1. F also has no unvisited neighbors remaining, so pop F.

  2. Now, you’re back at E. Its neighbor H is still unvisited, so you push H on the stack.

  1. Visiting H results in another dead end, so pop H.

  2. E also doesn’t have any available neighbors, so pop it.

  1. The same is true for B, so pop B.

  2. This brings you back to A, whose neighbor D still needs a visit, so you push D on the stack.

  1. Visiting D results in another dead end, so pop D.

  2. You’re back at A, but this time, there are no available neighbors to push, so you pop A. The stack is now empty, and the DFS is complete.

When exploring the vertices, you can construct a tree-like structure, showing the branches you’ve visited. You can see how deep DFS went when compared to BFS.

Implementation

Open the starter project for this chapter. This project contains an implementation of a graph, as well as a stack that you’ll use to implement DFS.

fun depthFirstSearch(source: Vertex<T>): ArrayList<Vertex<T>> {
  val stack = StackImpl<Vertex<T>>()
  val visited = arrayListOf<Vertex<T>>()
  val pushed = mutableSetOf<Vertex<T>>()

  stack.push(source)
  pushed.add(source)
  visited.add(source)
  
  // more to come ... 

  return visited
}
outer@ while (true) {
  if (stack.isEmpty) break

  val vertex = stack.peek()!! // 1
  val neighbors = edges(vertex) // 2

  if (neighbors.isEmpty()) { // 3
    stack.pop()
    continue
  }

  for (i in 0 until neighbors.size) { // 4
    val destination = neighbors[i].destination
    if (destination !in pushed) {
      stack.push(destination)
      pushed.add(destination)
      visited.add(destination)
      continue@outer // 5
    }
  }
  stack.pop() // 6
}
val vertices = graph.depthFirstSearch(a)
vertices.forEach {
  println(it.data)
}
A
B
E
H
F
C
G
D

Performance

DFS visits every vertex at least once. This has a time complexity of O(V).

Challenges

Challenge 1: Depth First Search

For each of the following two examples, which traversal (depth-first or breadth-first) is better for discovering if a path exists between the two nodes? Explain why.

Solution 1

  • Path from A to F: Use depth-first, because the path you’re looking for is deeper in the graph.
  • Path from A to G: Use breadth-first, because the path you’re looking for is near the root.

Challenge 2: Depth First Search

In this chapter, you went over an iterative implementation of depth-first search. Write a recursive implementation.

Solution 2

Let’s look at how you can implement DFS recursively.

fun depthFirstSearchRecursive(start: Vertex<T>): ArrayList<Vertex<T>> {
  val visited = arrayListOf<Vertex<T>>() // 1
  val pushed = mutableSetOf<Vertex<T>>() // 2

  depthFirstSearch(start, visited, pushed) // 3

  return visited
}
fun depthFirstSearch(
    source: Vertex<T>,
    visited: ArrayList<Vertex<T>>,
    pushed: MutableSet<Vertex<T>>
) {
  pushed.add(source) // 1
  visited.add(source)

  val neighbors = edges(source)
  neighbors.forEach { // 2
    if (it.destination !in pushed) {
      depthFirstSearch(it.destination, visited, pushed) // 3
    }
  }
}

Challenge 3: Depth First Search Challenge

Add a method to Graph to detect if a directed graph has a cycle.

Solution 3

A graph is said to have a cycle when there’s a path of edges and vertices leading back to the same source.

fun hasCycle(source: Vertex<T>): Boolean {
  val pushed = arrayListOf<Vertex<T>>() // 1
  return hasCycle(source, pushed) // 2
}
fun hasCycle(source: Vertex<T>, pushed: MutableSet<Vertex<T>>): Boolean {
  pushed.add(source) // 1

  val neighbors = edges(source) // 2
  neighbors.forEach {
    if (it.destination !in pushed && hasCycle(it.destination, pushed)) { // 3
      return true
    } else if (it.destination in pushed) { // 4
      return true
    }
  }

  pushed.remove(source) // 5
  return false // 6
}

Key points

  • Depth-first search (DFS) is another algorithm to traverse or search a graph.
  • DFS explores a branch as far as possible until it reaches the end.
  • Leverage a stack data structure to keep track of how deep you are in the graph. Only pop off the stack when you reach a dead end.
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
© 2024 Kodeco Inc.

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now