сортировка зависимостей с обнаружением циклических зависимостей

Question

Прежде чем вы начнете бросать мне в лицо ссылки на википедию и блоги, пожалуйста, выслушайте меня.

Я пытаюсь найти оптимальный алгоритм / функцию для сортировки зависимостей от ... вещей.У каждого элемента есть список его зависимостей.

Я хотел бы иметь что-то на основе итераторов, но это не очень важно.

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

Практически, я думаю о создании подкласса своих элементов из класса "узла зависимости", который имеет необходимые логические функции / функции для выполнения работы.Прикольные (но описательные) имена приветствуются :)

Answer 1

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

Answer 2

Я точно не понимаю, почему так сложно найти цикл зависимости, если он есть!вам просто нужно проверить, есть ли какой-либо узел, который вы уже пропустили при применении алгоритма bfs, чтобы выяснить все зависимости.если он есть, вы просто откатываетесь назад, чтобы вернуться к узлу, и отметить все узлы, пока не достигнете первого посещения указанного узла.все те, что в вашем проходе, будут помечены как цикл.(просто оставьте комментарий, и я дам код, чтобы сделать это, если вам нужно)