Что такое топологическая сортировка

Топологическая сортировка означает, что вам дается список заданий и список предварительных условий, и вы должны определить порядок заданий.

рабочие места = [1,2,3] предпосылки = [[1,2], [1, 3], [3,2]]

result = [1,3,2] должен быть порядком выполнения заданий. здесь [1,2] означает, что задание 2 не может быть запущено, пока задание 1 не будет завершено (задание 1 является предварительным условием).

Поэтому для этого вы можете использовать простой поиск в глубину (алгоритм обхода графа). в котором вы можете иметь собственный класс с именем JobVertex

class JobVertex {
   int job;
   List<JobVertex> preRequisites;
   boolean inProgress; 
   boolean visited;}

Изначально для флагов inProgress и посещений можно установить значение false. Флаг inProgress используется для обнаружения циклов (потому что для работы топологической сортировки граф должен быть DAG)

List<Integer> result = new ArrayList<>();

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

Временная сложность может быть такой же, как у dfs (v + e), где v соответствует вершинам, а e соответствует ребрам соответственно.

Топологическая сортировка — это линейный порядок узлов, в котором для каждого направленного ребра «a -> b» «a» стоит перед «b» в порядке. Поскольку ребра должны быть ориентированы, на ориентированных графах должны выполняться топологические сортировки, а графы также должны быть ациклическими (они не могут содержать циклы). Это специальное подмножество графов, известное как DAG (направленный ациклический граф).

Вот пример того, как это выглядит, обратите внимание, что все ребра (стрелки) идут слева направо