#c #sorting #graph-algorithm
#c #сортировка #граф-алгоритм
Вопрос:
Прежде чем вы начнете швырять мне в лицо ссылками на википедию и блоги, пожалуйста, выслушайте меня.
Я пытаюсь найти оптимальный алгоритм / функцию для выполнения сортировки зависимостей на … материале. У каждого элемента есть список его зависимостей.
Я хотел бы иметь что-то на основе итератора, но это не очень важно.
Важно то, что алгоритм точно указывает, какие элементы являются частью цикла зависимостей. Я хотел бы предоставить подробную информацию об ошибке в этом случае.
Практически, я подумываю о создании подкласса для моих элементов из класса «узел зависимости», в котором есть необходимые логические значения / функции для выполнения работы. Приветствуются интересные (но описательные) имена :)
Комментарии:
1. Вам нужен полный отчет по каждому циклу на графике или только по первому, который он обнаружит?
2. @Beta: первого будет достаточно, но я бы хотел полный цикл (что-то вроде a зависит от b, зависит от c зависит от a, а не просто «найдена циклическая зависимость для b»)
Ответ №1:
Обычно это называется топологической сортировкой. Большинство книг / статей / чего бы то ни было, что касается топологической сортировки, также, как само собой разумеющееся, будет охватывать обнаружение цикла.
Ответ №2:
Я не совсем понимаю, почему так сложно найти цикл dependecy, если он есть! вам просто нужно проверить, есть ли какой-либо узел, который вы уже пропустили при применении алгоритма bfs, чтобы узнать все зависимости. если таковая имеется, вы просто возвращаетесь к тому, как вы спустились, чтобы повторно посещать узел на всем пути вверх и отмечаете все узлы, пока не достигнете первого посещения указанного узла. все те, которые в вашем проходе, будут помечены как цикл. (просто оставьте комментарий, и я дам код для этого, если вам нужно)