На самом деле нужно просто руководствоваться: Топологическая сортировка по определению дуг (из моего вопроса) - это способ упорядочения всех дуг в направленном графе, чтобы все дуги, которые вставляются в вершину, должны появляться перед тем, из этой вершины.Топологическая сортировка по дугам
Не нужно ничего менять в топологической сортировке, вы можете просто использовать его и послепродавать.
высокий уровень псевдо-код:
arrlv в arr [упорядоченной итерации] : (v,u) в E: (v,u) to llПреимуществом этого метода является то, вы можете использовать топологическую сортировку, как черный ящик, не изменяя его и только после процесса, чтобы получить желаемый результат.
Корректность [Эскиз доказательства]:
Так как для каждого ребра (v,u) - u появляется после v в топологической сортировке, при печати, это делается с помощью v, и, таким образом, (v,u) печатается перед печатью любой вершины прилагается к u.
Сложность: O(|V|+|E|) топологическая сортировка, O(|V|+|E|) для последующей обработки [перебор всех вершин и всех ребер].
«Традиционная» топологическая сортировка сортирует вершины, а это сортирует дуги. В противном случае принцип тот же ...
Я знаю, но когда я смотрю в топологическом алгоритме сортировки, я не понимаю, как его можно изменить для дуг ... Не хочу, чтобы вы его разрешили, но мне нужно руководствоваться – Nusha
Перейти к вики страница, которую вы передали, раздел кода операции. Drop 'insert n в L' и на шаге, говорящем, что« удалить ребро e из графика », также« вставляем ребро e в L ». Таким образом вы будете помнить дуги вместо вершин. – tchap
Да, большой-O - это то же самое, но вам нужно сделать в два раза больше работы ... – tchap
@OndrejKupka: Действительно, константа будет выше, чем модификация топологической сортировки [хотя и не двойной, я полагаю, из-за производительности кеша] но в интересах ** инкапсулирования ** топологической сортировки. [это очень важный аспект!]. В реальных приложениях *, если вы обнаружите, что эта часть является горячей точкой *, вы, вероятно, захотите переписать ее, согласившись. – amit
Да, на самом деле не так просто копировать столько кода ни за что. – tchap