Discrete Mathsfor Engineers

6. Applications I

Depth-First Search is not only a traversal method. It is a structural tool that powers two classical applications: cycle detection and topological sorting.

In this part, we use the edge classification from Part 5 to solve concrete problems on directed graphs.

6.1 Why DFS Detects Cycles

DFS explores the graph recursively and keeps track of vertices that are currently active in the recursion stack.

If, during exploration, DFS reaches a vertex that is already active, then the search has returned to an ancestor.

6.2 Back Edges and Directed Cycles

From Part 5, a back edge is an edge from a vertex to one of its ancestors in the DFS tree.

Therefore:

6.3 Operational Test Using Colors

In practice, cycle detection is often implemented using DFS colors:

• WHITE — not discovered
• GRAY — currently active in recursion
• BLACK — fully explored

If DFS explores an edge (u, v) and finds v already GRAY, then (u, v) is a back edge, so a cycle exists.

6.4 Cycle Detection Sketch

A DFS-based cycle detector can be written as follows:

HAS-CYCLE(G):

    for each vertex u in V[G]:
        color[u] = WHITE

    for each vertex u in V[G]:
        if color[u] == WHITE:
            if DFS-CYCLE-VISIT(G, u):
                return true

    return false


DFS-CYCLE-VISIT(G, u):

    color[u] = GRAY

    for each v in Adj[u]:
        if color[v] == GRAY:
            return true
        if color[v] == WHITE:
            if DFS-CYCLE-VISIT(G, v):
                return true

    color[u] = BLACK
    return false

The algorithm stops as soon as it finds a back edge.

6.5 DAGs

A DAG is a Directed Acyclic Graph.

By the previous result:

DAGs are central in computer science because they model systems with dependencies but without circular requirements.

6.6 Topological Sorting — The Core Idea

A topological ordering of a directed graph is a linear ordering of its vertices such that for every edge (u, v), vertex u appears before v.

In a DAG, DFS finish times naturally produce such an order.

6.7 Finish Times and Ordering

In a DAG, for every edge (u, v), DFS guarantees:

Therefore, if we list vertices in decreasing order of finish time, every edge points forward in the list.

6.8 DFS-Based Topological Sort

A classical algorithm is:

TOPOLOGICAL-SORT(G):

    run DFS(G)

    return vertices sorted in decreasing order of f[u]

This works exactly when the graph is acyclic.

6.9 Engineering Use Cases

These two DFS applications appear constantly in practice:

• Cycle detection: validate dependency graphs, prevent circular imports, detect invalid prerequisite loops
• Topological sorting: order build steps, task execution, curriculum dependencies, job pipelines

6.10 Mini Summary

• Back edges characterize directed cycles.
• No back edge means the graph is a DAG.
• In DAGs, decreasing finish time gives a topological order.
• DFS is therefore a natural tool for dependency analysis.