Best Examples of Graph Traversal: Depth-First Search (DFS) Examples

Let’s start with the most basic example of depth-first search: exploring all vertices of an undirected graph using recursion.

Suppose we have this undirected graph with vertices labeled A through G:

• A is connected to B and C
• B is connected to A, D, and E
• C is connected to A and F
• D is connected to B
• E is connected to B and G
• F is connected to C
• G is connected to E

Assume we store neighbors in alphabetical order. A recursive DFS starting at A (call it DFS(A)) visits vertices in this order:

A → B → D → E → G → C → F

Why this order? DFS always goes as deep as it can:

• From A, it chooses B (alphabetically before C).
• From B, it goes to D (before E). D has no new neighbors, so it backtracks to B.
• Then B goes to E, which goes to G. G has no new neighbors, so we backtrack all the way to A.
• A still has C unvisited, so we go to C, then to F.

This is one of the best examples of graph traversal: depth-first search (DFS) examples for beginners because you can trace every decision: go deeper if possible, otherwise backtrack.

Directed Graph DFS: Reachability and Order

Another classic example of DFS involves a directed graph where direction matters. Consider this directed graph:

• A → B, A → C
• B → D
• C → D, C → E
• D → F
• E → F
• F has no outgoing edges

Run DFS from A, exploring neighbors in alphabetical order:

A → B → D → F → C → E

Here’s the reasoning:

• From A, we choose B first, then follow B → D → F.
• After F, there are no outgoing edges, so we backtrack: F → D → B → A.
• A still has C unvisited, so we go to C, then E, then backtrack.

This directed setting gives one of the clearest examples of graph traversal: depth-first search (DFS) examples for reachability: every node reachable from A ends up visited. It also shows how DFS naturally forms a depth-first forest (or a single tree, if the graph is connected from the start node).

If you want to see more formal treatments of DFS orderings and trees, the classic CLRS textbook (Introduction to Algorithms) is widely used in university courses, including those at MIT.

DFS vs. BFS: Maze and Pathfinding Example

One of the best examples to compare DFS and BFS is a grid maze.

Imagine a small 5×5 maze, where each open cell is a vertex and edges connect adjacent open cells (up, down, left, right). You start at the top-left cell (S) and want to reach the bottom-right cell (T).

• DFS behavior: It picks a direction (say, always try up, then right, then down, then left) and follows it as far as possible. It might snake deep into a dead-end corridor and only later backtrack. The path you find from S to T is a path, but not guaranteed to be the shortest in number of steps.
• BFS behavior: It explores layer by layer. The first time BFS reaches T, that path is guaranteed to be shortest in terms of edges.

This maze scenario is one of the most intuitive examples of graph traversal: depth-first search (DFS) examples because you can picture DFS as a single explorer walking through the maze, marking visited cells and occasionally walking back through the same corridors.

In practice, DFS is often preferred when:

• You care more about exploring all reachable states than about shortest paths.
• The graph is very large but relatively sparse, and recursion or a stack fits the available memory.

Cycle Detection: DFS on an Undirected Graph

Cycle detection is a classic example of how DFS solves real problems.

Take this undirected graph:

• 1 is connected to 2 and 3
• 2 is connected to 1 and 4
• 3 is connected to 1 and 4
• 4 is connected to 2 and 3

Visually, that’s a square: 1–2–4–3–1.

Run DFS starting from 1:

• From 1, go to 2.
• From 2, go to 4.
• From 4, you can go to 3 (unvisited) or 2 (already visited). If you reach a visited vertex that is not your immediate parent, you’ve found a cycle.
• From 4 to 3, you then see that 3 connects back to 1, which is again a visited vertex not equal to parent.

DFS gives a simple algorithm:

• For each unvisited vertex, run DFS.
• When exploring an edge (u, v):
  • If v is unvisited, continue DFS.
  • If v is visited and v ≠ parent[u], you have a cycle.

This is one of the cleanest examples of graph traversal: depth-first search (DFS) examples used in interview questions, often framed as “detect if an undirected graph has a cycle.”

Topological Sorting: DFS on a DAG (Dependency Example)

Now let’s move to a more applied scenario: software build systems and task scheduling.

Imagine you have tasks with dependencies:

• Task A must be done before B and C.
• Task B must be done before D.
• Task C must be done before D and E.
• Task D must be done before F.
• Task E must be done before F.

Represent this as a directed acyclic graph (DAG): edges go from prerequisite to dependent. This is the same structure as our earlier directed example, but now we care about topological order.

A typical DFS-based topological sort:

• Run DFS on each unvisited vertex.
• After you finish exploring all neighbors of a vertex, push it onto a stack or append it to a list.
• Reverse that list at the end.

On this graph, a valid topological order might be:

A, C, E, B, D, F

or

A, B, C, D, E, F

Both respect the dependency constraints.

This is one of the best real examples of graph traversal: depth-first search (DFS) examples because it lines up directly with real tools: build systems, package managers, and workflow engines often use DFS-like logic under the hood to order tasks. For a deeper theoretical treatment of DAGs and topological sorting, see open course notes from universities such as Princeton.

Web Crawling and Network Exploration Example

Consider a small portion of the web as a directed graph:

• Each page is a vertex.
• Each hyperlink from page X to page Y is a directed edge X → Y.

A simple example of graph traversal using DFS:

• Start from a seed page (say, your organization’s homepage).
• For each link on that page, recursively visit the linked page if you haven’t seen it before.
• Maintain a visited set to avoid infinite loops on cycles.

In practice, real web crawlers often use breadth-first or hybrid strategies to prioritize freshness and breadth. But DFS-style exploration is still used for:

• Deep auditing of a site section.
• Checking internal link consistency.
• Exhaustively exploring a bounded subgraph, such as all pages under /docs/.

This gives one of the more realistic examples of graph traversal: depth-first search (DFS) examples applied to networks, not just toy graphs.

For broader context on graph-based network analysis (including social networks and web graphs), you can explore materials from Stanford’s Network Analysis course.

DFS for Connected Components in an Undirected Graph

Another standard example of DFS use is finding connected components.

Imagine a social network graph where each vertex is a person and an undirected edge means “friends with.” The graph might not be one big cluster; it might split into several isolated groups.

DFS gives a simple pattern:

• Maintain a visited set and a component counter.
• For each vertex v:
  • If v is unvisited, start a DFS from v. All vertices reached belong to the same component.
  • Increment the component counter.

For instance, suppose you have:

• Component 1: {A, B, C} with edges A–B, B–C.
• Component 2: {D, E} with edge D–E.
• Component 3: {F} isolated.

DFS starting at A visits A, B, C and labels them component 1. DFS starting at D visits D, E and labels them component 2. F gets its own component.

This is one of the best examples of graph traversal: depth-first search (DFS) examples when teaching how to break a large graph into meaningful clusters.

DFS for Solving Puzzles: N-Queens and Backtracking

Many backtracking algorithms are just DFS on an implicit graph of states.

Take the classic N-Queens puzzle: place N queens on an N×N chessboard so that no two queens attack each other.

You can treat each partial board configuration as a vertex in a huge implicit graph. There is an edge from one configuration to another if you add a queen in a valid position in the next row.

A DFS-style backtracking algorithm:

• Start with an empty board (root state).
• At each row, try placing a queen in each column that is not attacked.
• Recursively continue to the next row.
• If you reach a conflict or run out of valid moves, backtrack.

This is a powerful example of graph traversal using DFS in a space where you never explicitly build the full graph. The graph exists logically; DFS explores only the parts it needs. This same pattern appears in Sudoku solvers, constraint satisfaction problems, and search in AI.

For a broader context on search algorithms and backtracking in AI, see open materials from courses like UC Berkeley’s CS 188, which discuss depth-first and related strategies.

2024–2025 Perspective: DFS in Modern Applications

If you think DFS is just a classroom curiosity, 2024–2025 trends say otherwise. Graph-based methods are central in modern data science and AI, and DFS remains a building block.

Some current directions where DFS-style traversal still matters:

• Graph neural networks (GNNs): While GNN training typically uses message passing rather than vanilla DFS, many preprocessing steps (extracting subgraphs, checking connectivity, pruning components) rely on DFS variants.
• Large-scale dependency graphs: Package managers, container orchestrators, and CI/CD pipelines use DFS to analyze dependency graphs and detect cycles or unreachable components before deployment.
• Security and vulnerability scanning: Tools that analyze call graphs, control-flow graphs, or network reachability often use DFS-based traversals to enumerate possible paths attackers might exploit.

These modern settings give more real examples of graph traversal: depth-first search (DFS) examples in production systems, not just in problem sets.

FAQ: DFS Examples and Common Questions

What are some standard examples of graph traversal: depth-first search (DFS) examples used in teaching?

Common teaching examples include:

• Exploring all vertices in a small undirected graph starting from a chosen node.
• DFS on a directed acyclic graph to produce a topological order.
• Cycle detection in undirected graphs using parent tracking.
• Maze exploration on a grid, where DFS finds a path from start to goal.

These give a good spread from basic mechanics to more applied tasks.

Can you give an example of DFS used in real-world software?

Yes. Build systems and package managers are classic real examples of graph traversal: depth-first search (DFS) examples. When you run a build, the tool must figure out which modules depend on which others and in what order to compile or link them. DFS-based topological sorting is a natural fit for this.

Why would I choose DFS over BFS in practice?

You might favor DFS when:

• You need to explore all reachable states, not just shortest paths.
• Memory is tight, and a BFS frontier might grow too large.
• You are implementing backtracking (like N-Queens, Sudoku, or general constraint solvers).

DFS is not always the best choice, but these cases are where it shines.

Is recursion always required for DFS?

No. Recursion is just a convenient way to express DFS. You can implement DFS iteratively by maintaining your own stack data structure. In fact, for very deep graphs, an explicit stack is often safer than recursion to avoid stack overflow.

How do I practice with more DFS examples?

You can:

• Work through graph problem sets from university courses, such as MIT OpenCourseWare or Princeton’s algorithms course.
• Use online judges and coding platforms that tag problems under “graph” and “DFS.”
• Take classic problems (maze solving, scheduling, puzzle solving) and explicitly model them as graphs, then implement DFS.

The more different settings you see, the easier it becomes to recognize when DFS is the right tool.

Depth-first search is not just a textbook algorithm; it’s a way of thinking about exploration, recursion, and structure. Once you internalize these examples of graph traversal: depth-first search (DFS) examples—from simple path tracing to dependency analysis and puzzle solving—you’ll start seeing DFS patterns in far more problems than you might expect.