Проверить корректность работы топологической сортировки
Как можно реализовать алгоритм проверки корректности топологической сортировки после выполнения программы, выдающей результат выполнения топологической сортировки? В силу неоднозначности данной сортировки (как, к примеру, для графа из трех вершин 1, 2, 3 со списком ребер 1->2, 1->3 существует два варианта сортировки 1, 2, 3; 1, 3, 2), существует ли какой-либо алгоритм проверки корректности?
Ответы (1 шт):
Как вариант проверки "корректности" (т.е. проверки того, что сортировка выполнена без нарушений порядка), вы можете пойти с конца отсортированного списка вершин и удалять по одной вершине. При удалении, проверяйте все ребра и если у какого-либо ребра эта вершина "дочерняя" - также удаляйте это ребро. Если у ребра эта вершина "родительская" - то сортировка была некорректной.
Другими словами - вы можете "отстригать хвост" и проверять, что ни одной обратной связи от него нет.
На картинке отметил арабскими и римскими порядок удаления вершин и ребер.