Топологическая сортировка

10.1 Определение топологической сортировки

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

Как вам определение? Если вы поняли его с первого раза, то, скорее всего, у вас есть большой опыт работы с алгоритмами.

Простыми словами это будет так: у вас есть список задач (вершины графа) и список зависимостей между ними (стрелки в графе). Расположите задачи (вершины) так, чтобы все задачи, от которых зависит «задача А», выполнялись до неё. И сразу всё понятно, а то «линейное упорядочение вершин ориентированного ациклического графа» …

Топологическая сортировка — очень важный алгоритм из практики, поэтому у него есть собственное имя, а не просто имя автора. Давайте разберёмся, где же он нужен:

Применение:

1. Планирование задач (Task Scheduling):

Определение порядка выполнения зависимых задач так, чтобы каждая задача выполнялась после всех её зависимостей.

Пример:

Планирование проектов в системе управления проектами.

2. Компиляция кода:

Определение порядка компиляции модулей или файлов исходного кода, которые зависят друг от друга.

Пример:

Оптимизация сборки программного обеспечения в системах сборки (например: Makefile).

3. Разрешение зависимостей в пакетных менеджерах:

Упорядочение пакетов так, чтобы все зависимости были установлены перед установкой самого пакета.

Пример:

Упрощение процесса установки программного обеспечения в пакетных менеджерах (например: npm, pip, apt).

4. Оптимизация маршрутов:

Определение порядка посещения точек или выполнения действий, учитывая зависимости между ними.

Пример:

Логистика и планирование маршрутов доставки товаров.

Временная и пространственная сложность топологической сортировки:

Временная сложность:

Оба основных алгоритма топологической сортировки (DFS и алгоритм Кана) имеют временную сложность O(V + E), где V — количество вершин, а E — количество рёбер в графе.

Пространственная сложность:

Пространственная сложность обоих алгоритмов составляет O(V + E), так как требуется хранение графа, а также массивов для отслеживания посещённых вершин и предшественников.

10.2 Реализация через поиск в глубину (DFS)

Топологическую сортировку можно выполнить разными способами, один из таких базируется на поиске в глубину — DFS. Алгоритм DFS для топологической сортировки использует стек для отслеживания завершённых узлов.

Пример реализации:

def topological_sort_dfs(graph):
    def dfs(vertex, visited, stack):
        visited.add(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                dfs(neighbor, visited, stack)
        stack.append(vertex)
        
    visited = set()
    stack = []
    for vertex in graph:
        if vertex not in visited:
            dfs(vertex, visited, stack)
            
    return stack[::-1]  # Результат в обратном порядке
    
# Пример использования:
graph = {
    'A': ['C'],
    'B': ['C', 'D'],
    'C': ['E'],
    'D': ['F'],
    'E': ['H', 'F'],
    'F': ['G'],
    'G': [],
    'H': []
}
result = topological_sort_dfs(graph)
print("Топологическая сортировка:", result)

Вывод:

Топологическая сортировка: ['B', 'D', 'F', 'G', 'A', 'C', 'E', 'H']

10.3 Реализация: алгоритм Кана

Ещё один подход называется алгоритм Кана (Kahn's Algorithm). Алгоритм Кана для топологической сортировки использует концепцию входящих степеней вершин.

Пример реализации:

from collections import deque, defaultdict

def topological_sort_kahn(graph):
    in_degree = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1
            
    queue = deque([u for u in graph if in_degree[u] == 0])
    top_order = []
            
    while queue:
        u = queue.popleft()
        top_order.append(u)
            
        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
            
    if len(top_order) == len(in_degree):
        return top_order
    else:
        raise ValueError("Граф содержит цикл")
            
# Пример использования:
graph = {
    'A': ['C'],
    'B': ['C', 'D'],
    'C': ['E'],
    'D': ['F'],
    'E': ['H', 'F'],
    'F': ['G'],
    'G': [],
    'H': []
}
result = topological_sort_kahn(graph)
print("Топологическая сортировка:", result)

Вывод:

Топологическая сортировка: ['A', 'B', 'D', 'C', 'E', 'H', 'F', 'G']

2

Задача

Модуль 1: Python Core, 17 уровень, 9 лекция

Недоступна

Топологическя сортировка

Топологическя сортировка

Открыть

2

Задача

Модуль 1: Python Core, 17 уровень, 9 лекция

Недоступна

Сортировка мусора

Сортировка мусора

Открыть

1

Опрос

Поиск в ширину и глубину, 17 уровень, 9 лекция

Недоступен

Поиск в ширину и глубину

Поиск в ширину и глубину

Открыть