В другой статье (Топологическая сортировка графа — реализация JavaScript) я реализую топологическую сортировку с использованием DFS, вот реализация алгоритма Кана, вдохновленная этим обучающим видео:

Алгоритм Кана

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

Пример графика

  • Подсчет входящей степени каждой вершины
    входящая степень : сколько ребер указывает на эту вершину
    входящая степень A = 0
    входящая степень B = 1
    Входящая степень D = 2
    …
  • Вершина без зависимостей означает, что ее входящая степень = 0.
  • Создайте очередь для хранения вершин без зависимостей и используйте индекс для отслеживания количества удалений, этот индекс может быть топологическим числом, связанным с удаленной вершиной.
  • Когда мы посещаем вершину и удаляем ее, мы уменьшаем входящую степень ее соседей, если входящая степень становится равной 0, добавляем ее в очередь.
  • Когда очередь пуста, либо все вершины удаляются, либо встречается цикл, то есть некоторые вершины остаются без посещения, но их входящая степень никогда не уменьшится до 0, потому что они указывают друг на друга.

Реализация JavaScript