Chapters
Chapters

Chapters

Hide chapters

Data Structures & Algorithms in Dart

Second Edition · Flutter · Dart 3.0 · VS Code 1.78

Before You Begin

Section 0: 6 chapters
Show chapters Hide chapters

Section I: Introduction

Section 1: 3 chapters
Show chapters Hide chapters

Section II: Elementary Data Structures

Section 2: 3 chapters
Show chapters Hide chapters

Section III: Trees

Section 3: 9 chapters
Show chapters Hide chapters

Section IV: Sorting Algorithms

Section 4: 5 chapters
Show chapters Hide chapters

Section V: Graphs

Section 5: 5 chapters
Show chapters Hide chapters

Section VI: Challenge Solutions

Section 6: 21 chapters
Show chapters Hide chapters

23. Depth-First Search
Written by Jonathan Sande

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

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 a lot of 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 backtrack and explore the next available branch until you find what you’re looking for or until you’ve visited all the vertices.

How Depth-First Search Works

The following example will take you through a depth-first search. The graph below is the same as the one in the previous chapter so you can see the difference between BFS and DFS.

D C H G F E B A

BFS used a queue to visit neighboring vertices first. However, DFS will use a stack to keep track of the levels you move through. The stack’s last-in-first-out approach helps with backtracking. Every push on the stack means that you move one level deeper. You can pop to return to a previous level if you reach a dead end.

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

A Stack H D B E A F G C

As long as the stack isn’t empty, you visit the top vertex on the stack and push the first neighboring vertex that has yet to be visited. In this case, you visit A and push B:

A B Stack H D B E A F G C

Remember that the order in which the edges were added influences the search result. In this case, the first edge added to A was to B, so B is pushed first.

You visit B and push E because A is already visited:

A B E Stack H D B E A F G C

Every time you push onto the stack, you advance farther down a branch. Instead of visiting every adjacent vertex, you continue down a path until you reach the end. After that, you backtrack.

Next, visit E and push F.

A B E F Stack H D B E A F G C

Again, the only reason you chose F instead of H is that F happened to be added first when the graph was created for this particular example. You can’t see that from the diagram, but when you get to the code later on, you’ll be able to observe the edge addition order.

Now visit F and push G:

A B E F G Stack H D B E A F G C

Then visit G and push C:

A B E F G C Stack H D B E A F G C

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

C A B E F G Stack H D B E A F G C

This brings you back to G. It has neighbors [F, C], but both of these have been visited. Another dead end, so pop G:

G C A B E F Stack H D B E A F G C

F also has no unvisited neighbors remaining, so pop F:

C G F A B E Stack H D B E A F G C

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

C G F A B E H Stack H D B E A F G C

Visiting H results in another dead end, so pop H:

C G F H A B E Stack H D B E A F G C

E doesn’t have any available neighbors either, so pop it:

C G F H E A B Stack H D B E A F G C

The same is true for B, so pop B:

C G F H E B A Stack H D B E A F G C

This brings you all the way back to A, whose neighbor D still needs to be visited, so you push D on the stack:

C G F H E B A D Stack H D B E A F G C

Visiting D results in another dead end, so pop D:

C G F H E B D A Stack H D B E A F G C

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 DFS is complete!

C G F H E B D A Stack H D B E A F G C

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

Breadth-First Search A H B D C E F G H A B E D F G C Depth-First Search

Implementation

Open up the starter project for this chapter. The lib folder contains an implementation of a graph as well as a stack, both of which you’ll use to implement DFS.

Creating an Extension

Create a new file in lib called depth_first_search.dart. Add the following:

Traversing Vertices

Next, complete the method by replacing the // more to come comment with the following:

Testing it Out

To try out your code, open bin/starter.dart and replace the contents of the file with the following code:

Performance

DFS will visit every single vertex at least once. This process has a time complexity of O(V).

Cycles

A depth-first search is also useful for finding whether a graph contains cycles. A graph is said to have a cycle when a path of edges and vertices leads back to the same source.

U R V M

Checking for Cycles

Next, you’ll write an algorithm to check whether a directed graph contains a cycle.

Testing it Out

To create a graph that matches the image above, open bin/starter.dart and replace the content of main with the following:

Challenges

Try out the following challenges to test your understanding of depth-first searches. You can find the answers in the back of the book or in the supplemental materials that accompany the book.

Challenge 1: BFS or DFS

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.

O G W P K J Q

Challenge 2: Recursive DFS

In this chapter, you learned an iterative implementation of depth-first search. Now write a recursive implementation.

Key Points

  • Depth-first search (DFS) is another algorithm to traverse or search a graph.
  • DFS explores a branch as far as possible before backtracking to the next branch.
  • The stack data structure allows you to backtrack.
  • A graph is said to have a cycle when a path of edges and vertices leads back to the source vertex.
22. Breadth-First Search
24. Dijkstra’s Algorithm
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.
© 2026 Kodeco Inc.

You’re accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now