Топологическая сортировка по дугам

Question

Действительно нужны только некоторые указания: Топологическая сортировка по определению дуг (из моего вопроса) - это способ упорядочения всех дуг в графе направленности, поэтому все дуги, которые вставляются в вершину, должны появиться раньше, чем та, которая выходит из этой вершины.

Answer 1

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

псевдокод высокого уровня:

1. запустить топологическую сортировку,результирующий массив будет arr
2. создать пустой список ребер, пусть он будет l
3. для каждой вершины v в arr [упорядоченная итерация]:
   3.1.за каждый (v,u) в E:
   3.1.1.append (v,u) to l
4. return l

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

Корректность [эскиз доказательства]:
Так как для каждого ребра (v,u) - u появляется после v в топологической сортировке,когда вы его печатаете, это делается через v, и, таким образом, (v,u) печатается до того, как вы напечатаете любую вершину, прикрепленную к u.

Сложность :
O(|V|+|E|) топологическая сортировка, O(|V|+|E|) для постобработки [повторение всех вершин и всех ребер].

Answer 2

«Традиционная» топологическая сортировка - это сортировка вершин, в то время как эта сортирует дуги. В остальном принцип тот же ...