Перейти к содержимому
Skein

алгоритм Kahn

EN: Kahn's algorithm

Топологическая сортировка, которая вычисляет полустепень захода каждой вершины, помещает в очередь все вершины с полустепенью 0, затем многократно извлекает одну в вывод и уменьшает полустепени её соседей, добавляя в очередь те, у кого она достигла 0. Если в выводе меньше вершин, чем в графе, значит, есть цикл. Работает за O(V + E).

хоткеиразвернуть
поиск
⌘K
пред. пьеса
k
след. пьеса
j
тиры
t
это меню
?