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

Question

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

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

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

Answer 1

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

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

Answer 2

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

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