Topological Sort

Topological Sort is used to create a ranking of a DAG. If passed in a DAG, it returns one possible path through the graph by dfsing through it.

Using a Library:

from graphlib import TopologicalSorter

def topological_sort(graph):
    ts = TopologicalSorter()
    for key, value in graph:
        ts.add(key, *value)
    try:
        ts.static_order()
    except CycleError:
        return []

def topological_sort(graph, node):
    result = []
    seen = set()

    def recursive_helper(node):
        for neighbor in graph[node]:
            if neighbor not in seen:
                seen.add(neighbor)
                recursive_helper(neighbor)
        result.append(node)

    recursive_helper(node)
    return list(reversed(result))

This takes O |V| + |E| or (O(n)) time.