10.1 Визначення топологічного сортування
Топологічне сортування — це лінійне упорядкування вершин орієнтованого ациклічного графу (DAG) таке, що для кожного ребра (u, v) вершина u передує вершині v. Це упорядкування можливе лише для DAG і не може бути виконане на графах, які містять цикли.
Як тобі визначення? Якщо ти зрозумів його з першого разу, то, швидше за все, у тебе є великий досвід роботи з алгоритмами.
Простими словами це буде так: у тебе є список завдань (вершини графа) і список залежностей між ними (стрілки в графі). Розташуй завдання (вершини) так, щоб усі завдання, від яких залежить «задача A», виконувалися до неї. І відразу все зрозуміло, а то «лінійне упорядкування вершин орієнтованого ациклічного графа» …
Топологічне сортування — дуже важливий алгоритм з практики, тому у нього є власна назва, а не просто ім'я автора. Давайте розберемося, де ж він потрібний:
Застосування:
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']
ПЕРЕЙДІТЬ В ПОВНУ ВЕРСІЮ