How can Topological Sort be implemented using DFS?

A topological sort can be achieved by performing a Depth-First Search (DFS) on a Directed Acyclic Graph (DAG). After a node has been fully explored (i.e., all its descendants have been visited), it is prepended to a list. The final list represents the topologically sorted order.

What is the role of the visited set in a DFS-based topological sort?

In a DFS-based topological sort, a 'visited' set is crucial for tracking the state of each node. It typically has three states: unvisited, visiting (currently in the recursion stack), and visited. This helps in detecting cycles, as encountering a 'visiting' node indicates a back edge and thus a cycle.

Graph Algorithms

Topological Sort: DFS Approach

A powerful, recursive method for ordering tasks in a Directed Acyclic Graph (DAG), the DFS-based topological sort is a cornerstone of graph theory interviews.

DFS Topological Sort in Python

Here is a Python implementation of topological sorting using Depth-First Search.

def topological_sort_dfs(graph):
    visited = set()
    recursion_stack = set()
    result = []

    def dfs(u):
        visited.add(u)
        recursion_stack.add(u)

        for v in graph.get(u, []):
            if v not in visited:
                if not dfs(v):
                    return False
            elif v in recursion_stack:
                return False  # Cycle detected

        recursion_stack.remove(u)
        result.insert(0, u)
        return True

    for u in list(graph):
        if u not in visited:
            if not dfs(u):
                return []  # Cycle detected

    return result

AI Coach Hint: The key to the DFS-based topological sort is adding the vertex to the *front* of the result list *after* visiting all its neighbors. This ensures that a vertex appears before all vertices it has edges to.