Сортировка графика так, чтобы как можно больше стрелок указывало вперед

Question

Мне нужно отсортировать узлы ориентированного графа таким образом, чтобы количество стрелок, обращающихся назад (против порядка сортировки), было минимальным.

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

Как называется и сложность этой проблемы?

Answer 1

Сортировка узлов по глубине может быть выполнена с помощью топологической сортировки . Однако это будет работать только с графами, которые не содержат циклов. Ваша проблема звучит так, как будто на графике есть циклы. Один из вариантов - найти циклы (см. Алгоритм Черепаха и Заяц , чтобы узнать, как это сделать) и разорвать цикл, записав, где вы его сломали. Затем сортируйте узлы и повторно связывайте.

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

Answer 2

Подумав, я понял, что проблему можно разделить на две части:

1. определяет самый большой ациклический подграф графа (который является NP-сложным )
2. топологически сортируйте его (что намного проще )