中文
devexamples

Graph DFS Topological Sort (Python)

Perform topological sort on a DAG using DFS with cycle detection via tri-color marking.

PythonData Integrity

Code

snippet
def topological_sort(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {n: WHITE for n in graph}
    result = []

    def dfs(node):
        if color[node] == GRAY:
            raise ValueError(f"cycle at {node}")
        if color[node] == BLACK:
            return
        color[node] = GRAY
        for neighbor in graph.get(node, []):
            dfs(neighbor)
        color[node] = BLACK
        result.append(node)

    for n in graph:
        if color[n] == WHITE:
            dfs(n)
    return result[::-1]

Related Examples