Топологическая сортировка — это фундаментальный алгоритм в теории графов, используемый для линейного упорядочения вершин ориентированного ациклического графа (DAG) на основе их зависимостей. Несмотря на то, что существует множество доступных алгоритмов топологической сортировки, в этой статье особое внимание уделяется подходам на основе памяти, которые отдают приоритет эффективности. Мы рассмотрим несколько методов и предоставим примеры кода, иллюстрирующие их реализацию.

Метод 1: алгоритм Кана
Алгоритм Кана — это классический метод топологической сортировки, известный своей простотой. Он использует подход на основе очередей для идентификации и обработки вершин с нулевым количеством входящих ребер.

def topological_sort_kahn(graph):
    # Calculate in-degrees of all vertices
    in_degrees = {v: 0 for v in graph}
    for v in graph:
        for neighbor in graph[v]:
            in_degrees[neighbor] += 1

    # Enqueue vertices with zero in-degree
    queue = [v for v in graph if in_degrees[v] == 0]

    # Perform topological sorting
    result = []
    while queue:
        vertex = queue.pop(0)
        result.append(vertex)
        for neighbor in graph[vertex]:
            in_degrees[neighbor] -= 1
            if in_degrees[neighbor] == 0:
                queue.append(neighbor)

    if len(result) != len(graph):
        # Graph contains a cycle
        return None
    return result

Метод 2: поиск в глубину (DFS) с рекурсией
DFS — еще один широко используемый метод топологической сортировки. Выполняя рекурсивный обход графа, мы можем упорядочить вершины на основе их последующего обхода.

def topological_sort_dfs(graph):
    visited = set()
    result = []
    def dfs(vertex):
        visited.add(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                dfs(neighbor)
        result.append(vertex)
    for vertex in graph:
        if vertex not in visited:
            dfs(vertex)
    return result[::-1]

Метод 3: поиск в глубину (DFS) со стеком
DFS также можно реализовать итеративно с использованием стека. Поддерживая стек вершин и отмечая посещенные узлы, мы можем эффективно добиться топологической сортировки.

def topological_sort_dfs_stack(graph):
    visited = set()
    stack = []
    result = []
    for vertex in graph:
        if vertex not in visited:
            stack.append(vertex)
            while stack:
                current = stack[-1]
                visited.add(current)
                has_unvisited_neighbors = False
                for neighbor in graph[current]:
                    if neighbor not in visited:
                        stack.append(neighbor)
                        has_unvisited_neighbors = True
                if not has_unvisited_neighbors:
                    result.append(stack.pop())
    return result[::-1]

Метод 4: модифицированный поиск в глубину (DFS) с метками пост-порядка
Этот подход модифицирует алгоритм DFS, присваивая каждой вершине метки пост-порядка. Метки используются для определения порядка вершин в результате топологической сортировки.

def topological_sort_dfs_postorder(graph):
    visited = set()
    post_order = {}
    label = len(graph)
    def dfs(vertex):
        nonlocal label
        visited.add(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                dfs(neighbor)
        post_order[vertex] = label
        label -= 1
    for vertex in graph:
        if vertex not in visited:
            dfs(vertex)
    result = [vertex for vertex, _ in sorted(post_order.items(), key=lambda x: x[1])]
    return result

В этой статье мы рассмотрели различные алгоритмы топологической сортировки на основе памяти. Мы обсудили алгоритм Кана, DFS с рекурсией, DFS со стеком и модифицированную DFS с метками пост-порядка. Каждый метод имеет свои преимущества и подходит для разных сценариев. Понимая эти подходы и их реализацию кода, вы сможете выбрать наиболее подходящий алгоритм с учетом конкретных требований вашего проекта.

Помните, что эффективная топологическая сортировка имеет решающее значение при работе с большими графиками или приложениями, чувствительными ко времени. Учитывайте характеристики вашего графика и временную сложность каждого алгоритма, чтобы принять обоснованное решение. Удачной сортировки!