Предположим, у нас есть направленный ациклический c граф G, для которого мы выполняем топологическую сортировку (топологически отсортированные вершины обозначим через v 1 , v 2 , ... ., v n . Однако предположим, что три ссылки v i , v i + 1 , v i + 2 вставлены в ссылку список в обратном порядке (см. строку 2 топологической сортировки), то есть они должны были быть вставлены в список ссылок как v i + 2 → v i + 1 → v i ; но они вставляются как v i → v i + 1 → v i + 2 . Это означает, что некоторые ребра могут нарушать топологическую сортировку. максимальное число ребер, которые могут нарушать топологическую сортировку. Объясните ваш ответ. Если вы даете i и знаете, что вершины помечены как v i , v i + 1 и v i + 2 вставлены в топологическую сортировку задом наперед, описывают алгоритм, который печатает ребра, нарушающие топологическую сортировку . Предположим, у вас есть матрица смежности и столбцы организованы этими подписками. Каково время работы алгоритма?
TOPOLIGICAL-SORT(G) = (V,E)
1. CALL DFS(G) to compute finish times v.f for each vertex v
2. as each vertex is finished, insert it into the front of a linked list
3. return the linked list of vertices
У меня проблемы с написанием алгоритма для этого. Я знаю, что столбец матрицы смежности имеет порядок (v 1 , v 2 , ...., v n ). Не могли бы вы помочь мне понять, как придумать максимальное количество неправильных ребер и написать четкий алгоритм для него? Я очень смущен. Спасибо за ваше время и помощь!